halo2 Crates.io

重要提示: 这个库正在积极开发中,不应该在生产软件中使用.

文档

最低支持的 Rust 版本

需要 Rust 1.51 或者更高.

最低支持的 rust 版本 可以在 未来更改, 但是这会带来小版本的改变

并行控制方案

halo2 当前为并行计算使用 rayon . 设置 线程数量数量时使用 RAYON_NUM_THREADS 环境变量

许可证

Copyright 2020-2021 The Electric Coin Company.

你可以在 Bootstrap 开源许可证 1.0 版下使用这个包, 或者您可以选择任意更高版本 . 看这个文件 COPYING 去了解更多详细信息, 看这个文件 LICENSE-BOSL 了解 Bootstrap 开源许可证 1.0 版条款.

BOSL的目的是允许对包进行商业改进,同时确保所有改进都是开源的 . 看 去了解 BOSL 为什么存在.

概念

首先,我们将描述零知识证明系统背后的概念; halo 2 所使用的算法(一种电路描述); 以及我们用来构建电路实现的抽象概念

Proof systems

证明系统 的目标是能够证明有趣的数学或密码学语句.

Typically, in a given protocol we will want to prove families of statements that differ in their public inputs. The prover will also need to show that they know some private inputs that make the statement hold.

通常,在给定的协议中,我们想要证明不同于它们的公共输入的语句族。 证明者需要展示他们知道一些隐私输入来使语句成立

To do this we write down a relation, , that specifies which combinations of public and private inputs are valid.

为了做到上面所说的, 我们描绘了一个关系式, , 这个关系式指定哪些公共输入和隐私输入组合是有效的。

The terminology above is intended to be aligned with the ZKProof Community Reference.

上面的术语和 ZKProof Community Reference 是一致的

To be precise, we should distinguish between the relation , and its implementation to be used in a proof system. We call the latter a circuit.

准确地说,我们应该区分关系式 和它在证明系统中使用的实现。我们称后者为电路。

The language that we use to express circuits for a particular proof system is called an arithmetization. Usually, an arithmetization will define circuits in terms of polynomial constraints on variables over a field.

我们用来表示特定证明系统的电路的语言叫做arithmetization。 通常,一个算法会在多项式约束条件下定义电路,多项式中的变量在一个域中 。

The process of expressing a particular relation as a circuit is also sometimes called "arithmetization", but we'll avoid that usage.

表达一个特定关系的过程叫做电路, 有时也叫作 "算法", 但是我们避免这种称呼.

To create a proof of a statement, the prover will need to know the private inputs, and also intermediate values, called advice values, that are used by the circuit.

为了去创建一个语句的proof, 证明者需要知道 private input, 还有电路使用的中间值,又称为通知值。

We assume that we can compute advice values efficiently from the private and public inputs. The particular advice values will depend on how we write the circuit, not only on the high-level statement.

我们假设我们能高效的通过公开输入和隐私输入计算通知值. 具体的通知值依赖于于我们如何编写电路,而不仅仅取决于高级语句。

The private inputs and advice values are collectively called a witness.

隐私输入和通知值共同叫做 witness

Some authors use "witness" as just a synonym for private inputs. But in our usage, a witness includes advice, i.e. it includes all values that the prover supplies to the circuit.

有些作者在写 隐私输入时使用witness, 但是在我们的使用中, witness还包括 通知值, 即它包括证明者提供给电路的所有值。

For example, suppose that we want to prove knowledge of a preimage of a hash function for a digest :

举个例子

  • The private input would be the preimage .

  • 隐私输入是 原像

  • The public input would be the digest .

  • 公开输入是

  • The relation would be .

  • 关系式为 .

  • For a particular public input , the statement would be: .

  • 对于特定的公共输入 , 语句是.

  • The advice would be all of the intermediate values in the circuit implementing the hash function. The witness would be and the advice.

  • advice是实现哈希函数的电路中的所有中间值。witness是和advice。

A Non-interactive Argument allows a prover to create a proof for a given statement and witness. The proof is data that can be used to convince a verifier that there exists a witness for which the statement holds. The security property that such proofs cannot falsely convince a verifier is called soundness.

非交互式argument允许prover给给定的语句和witness创建一个proof. 证明是一个可以使验证者确信存在witness 并使数据成立的数据. 这种证明不能错误地说服验证者的安全特性称为可靠性。

A Non-interactive Argument of Knowledge (NARK) further convinces the verifier that the prover knew a witness for which the statement holds. This security property is called knowledge soundness, and it implies soundness.

非交互式证明(NARK)进一步使验证者确信证明者知道使语句成立的witness. 这个安全属性称为知识可靠性,它暗示了可靠性。

In practice knowledge soundness is more useful for cryptographic protocols than soundness: if we are interested in whether Alice holds a secret key in some protocol, say, we need Alice to prove that she knows the key, not just that it exists.

在实践中,知识的可靠性对于密码协议比可靠性更有用 : 如果我们对Alice是否在某个协议中持有密钥感兴趣,我们需要Alice证明她知道密钥,而不仅仅是密钥存在。

Knowledge soundness is formalized by saying that an extractor, which can observe precisely how the proof is generated, must be able to compute the witness.

知识的可靠性是通过一个提取器来形式化的,它可以精确地观察证明是如何生成的,能够计算witness。

This property is subtle given that proofs can be malleable. That is, depending on the proof system it may be possible to take an existing proof (or set of proofs) and, without knowing the witness(es), modify it/them to produce a distinct proof of the same or a related statement. Higher-level protocols that use malleable proof systems need to take this into account.

这个性质是微妙的,因为证明是可塑的。 也就是说,根据证明系统,可以采用现有的证明(或者证明集) 在不知道witness的情况下,修改witness 生成一个明显相同的证明或者是一个有关的语句. 修改证人的陈述,以提供有关陈述的清晰证明。 使用可塑证明系统的高级协议需要考虑到这一点.

Even without malleability, proofs can also potentially be replayed. For instance, we would not want Alice in our example to be able to present a proof generated by someone else, and have that be taken as a demonstration that she knew the key.

即使没有可塑性, 证明也很可能回放, 举个例子, 我们不希望在我们的例子中Alice能够提交别人生成的证明,并将其作为她知道密钥的证明。

If a proof yields no information about the witness (other than that a witness exists and was known to the prover), then we say that the proof system is zero knowledge.

如果一个证明中没有关于witness的信息(除此之外, witness存在并且prover 知道witness), 这时我们说证明系统是 零知识的

If a proof system produces short proofs —i.e. of length polylogarithmic in the circuit size— then we say that it is succinct. A succinct NARK is called a SNARK (Succinct Non-Interactive Argument of Knowledge).

如果证明系统生成了简短的证明, 即 ? 那么我们说这时 简洁的 一个简介的NARK 叫做 snark(简洁的非交互式证明)

By this definition, a SNARK need not have verification time polylogarithmic in the circuit size. Some papers use the term efficient to describe a SNARK with that property, but we'll avoid that term since it's ambiguous for SNARKs that support amortized or recursive verification, which we'll get to later.

根据这个定义, 一个SNARK 不需要? 有些论文使用术语efficient来描述具有这种性质的SNARK, 但我们将避免使用这个术语,因为它对于支持平摊或递归验证的SNARKs来说是语义是模糊的,我们稍后会讲到

A zk-SNARK is a zero-knowledge SNARK.

zk-SNARK 叫做零知识证明

PLONKish 算法

halo2 使用的运算方法 来自于 PLONK, 或者更准确地说,它的扩展UltraPLONK支持自定义门和查找arguments. 我们称之为 PLONKish.

PLONKish电路是用矩形矩阵值定义的. 我们称呼矩阵的单元格 用常规的称呼。

PLONKish电路依赖配置

  • 一个有限域,其中单元格的值(对于给定的statement和witness)将是的元素.

  • The number of columns in the matrix, and a specification of each column as being fixed, advice, or instance. Fixed columns are fixed by the circuit; advice columns correspond to witness values; and instance columns are normally used for public inputs (technically, they can be used for any elements shared between the prover and verifier).

  • 矩阵中列的数量, 以及每个列的参数是固定通知还是实例. 固定列是固定在电路中的. 通知列和witness 值一致. 实例列通常用于公开输入( 确切来说, 它们可以用于prover和verifier之间共享的任何元素).

  • A subset of the columns that can participate in equality constraints.

  • 可以参与相等约束的列的子集。

  • A polynomial degree bound.

  • 多项式次数约束

  • A sequence of polynomial constraints. These are multivariate polynomials over that must evaluate to zero for each row. The variables in a polynomial constraint may refer to a cell in a given column of the current row, or a given column of another row relative to this one (with wrap-around, i.e. taken modulo ). The maximum degree of each polynomial is given by the polynomial degree bound.

  • 一个多项式约束的序列. 这是在 上的每行必须为0的多元多项式. 多项式约束中的变量可以指当前行的给定列中的单元格,也可以指与这行(即取模n)相关的另一行的给定列 每个多项式的最高次由这个多项式次数给出.

  • A sequence of lookup arguments defined over tuples of input expressions (which are multivariate polynomials as above) and table columns.

  • 一个查找 arguments输入表达式(多元多项式)的元组和表列上定义

A PLONKish circuit also defines:

PLONKish电路还定义:

  • The number of rows in the matrix. must correspond to the size of a multiplicative subgroup of ; typically a power of two.

  • 矩阵的行数为 . 必须对应于 的可乘子群的大小;通常是 2的幂次方.

  • A sequence of equality constraints, which specify that two given cells must have equal values.

  • 一个由相等约束组成的数组,数组中指定两个给定单元格必须具有相等的值

  • The values of the fixed columns at each row.

  • 每行中固定列的值

From a circuit description we can generate a proving key and a verification key, which are needed for the operations of proving and verification for that circuit.

从电路描述中我们可以生成 电路的证明和验证操作所需要的 一个 证明key 和 一个 验证key

Note that we specify the ordering of columns, polynomial constraints, lookup arguments, and equality constraints, even though these do not affect the meaning of the circuit. This makes it easier to define the generation of proving and verification keys as a deterministic process.

请注意,我们指定了列的顺序、多项式约束、查找参数和等式约束,即使这些并不影响电路的含义。 这使得将证明和验证密钥的生成定义为确定性过程变得更加容易。

Typically, a configuration will define polynomial constraints that are switched off and on by selectors defined in fixed columns. For example, a constraint can be switched off for a particular row by setting . In this case we sometimes refer to a set of constraints controlled by a set of selector columns that are designed to be used together, as a gate. Typically there will be a standard gate that supports generic operations like field multiplication and division, and possibly also custom gates that support more specialized operations.

通常,配置将定义多项式约束,这些约束由定义在固定列中的选择器关闭和开启。 例如,约束 可以通过在第i行设置来关闭。 在这种情况下,我们有时引用一组由一组选择器列控制的约束,这些选择器列被设计为一起使用,就像一个gate。 通常会有一个标准门, 它支持像字段乘法和除法这样的通用操作,也可能有一个支持更专用操作的自定义门.

芯片

在先前的章节中, 提到了 一个低层次的电路描述. 在实现电路时, 我们通常会使用以可审核性、效率、模块化和可表达性为目标的高层次的api

在api中使用的一些术语和概念是类比于集成电路的设计和布局.关于集成电路, 通过组合特定功能的高效预编译的 芯片 更容易获得上述理想的特性.

举个例子, 我们可能有 实现特定密码学原语 的芯片, 比如说 哈希函数, 或者加密算法 或者像标量乘法或配对这样的算法.

在UPA中,仅仅有执行域乘法和加法的标准门电路就可以建立任意逻辑, 然而, 使用自定义门电路可以获得非常显著的效率增益.

使用我们的API, 我们定义了"知道" 如何使用特定的自定义门集合的芯片. 这创建了一个将高级电路的实现与直接使用自定义门的复杂性隔离开的抽象层.

尽管有时我们需要 "身兼两职", 既写高层次的电路, 也要写高层次电路所需要的芯片. 这样做的目的是使代码更易于理解、审计和维护/重用. 通过这种结构排除了一些潜在的实现的错误.

UPA中的门通过 相对引用 引用单元格,即给定列中的单元格,以及相对于设置门选择器的给定偏移量的行. 当偏移非0时, 我们称之为 偏移参考 (也就是说, 偏移引用是 相对引用的子集).

绝对引用 对比, 相对引用使用了相同的约束, 能指向任意单元格

偏移引用的动机是减少配置中列的数量,从而减少证明的大小. 如果没有偏移引用,则需要一个列来保存自定义门引用的每个值, 以及我们需要使用相同的约束从电路的其他单元复制值到该列中. 使用偏移引用, 我们不仅需要更少的列, 我们也不需要为所有这些列支持相同的约束,这可以提高效率.

在R1CS(对于一些读者来说,可能这个算法更熟悉, 如果不是,也不要担心), 电路包含了无语义重要顺序的海量的门. 另一方面, 因为偏移引用, UPA电路中的行顺序 重要的 我们做一些简单的假定和定义一些抽象概念来控制结构的复杂性: 目的就是这样, 在工具层, 我们做了大多数的电路构造, 我们不处理相对引用或者是明确的门布局.

我们把一个电路分到一个 范围 中, 每一个范围都包含着一个不相交的单元格子集, 相对引用只指向 一个区域. 芯片实现的部分职责是确保进行偏移引用的门被放置在区域的正确位置。

给定区域集合和形状, 我们将使用一个单独的 平面规划器 来决定每个区域放置在哪里(即起始行在哪里)。 有一个实现了通用算法的默认 平面规划器, 在你需要时, 你可以写你自己的 平面规划器.

平面规划一般会在矩阵中留下空隙, 因为在给定的行中,电路门没有使用所有可用的列. 它们尽可能由不需要偏移引用的门填充,这允许它们被放置在任何行上。

芯片也定义了查找表. 如果同一个查找 argument 定义了多个表, 可以使用标记列指明 每行使用了哪一个表. 也可能对多个表(受多项式次数界的限制)进行联合查找.

芯片组合

为了将几个芯片的功能结合起来,我们将它们组合在一棵树上. 最高层次的芯片定义一组固定列、通知列和实例列,然后指定它们应该如何在较低级别芯片之间分布。

在最简单的情况下,每个低层次芯片将使用与其他芯片分离的列。然而,在芯片之间共享一列也是允许的。 优化advice列的数量尤其重要,因为这会影响证明的大小。

结果(可能在优化之后)是一个UPA配置。我们的电路实现将在芯片上参数化, 并且可以通过顶层次芯片使用支持的底层芯片的任何特性。

我们希望不那么专业的用户通常能够找到支持他们需要的操作的现有芯片, 或者只需要对现有芯片做微小的修改。专家级用户可以完全控制[] 电路优化 的种类.

Our hope is that less expert users will normally be able to find an existing chip that supports the operations they need, or only have to make minor modifications to an existing chip. Expert users will have full control to do the kind of circuit optimizations that ECC is famous for 🙂.

工具

当实现一个电路时,我们可以直接使用我们选择的芯片的特性。 通常, 我们会通过 工具 使用他们. 这种间接方式是很有用的,因为由于效率和UPA的限制,芯片接口通常依赖于底层的实现细节. 工具接口可以提供更加便捷和稳定的, 从无关细节抽象化的 api

举个例子, 想一个哈希函数, 比如说 SHA-256. 芯片的接口支持 SHA-256 可能是依赖于内部的哈希函数设计, 例如消息调度和压缩功能之间的分离功能. 一致的工具接口可以提供更加便捷和熟悉的 更新/完成 API, 也能够在不需要芯片支持的情况下处理hash函数的一部分, 比如说 填充 功能. 这类似于通常通过软件库而不是直接访问cpu上加密原语的加速 指令

工具能在高层次上为电路程序提供一个模块化,可重用的抽象概念, 类似于在像 libsnark, bellman 这样的库中使用. 不但需要 抽象 函数, 同样也需要抽象 类型, 例如特定大小的椭圆曲线上的点或整数类型.

用户手册

你来这里可能是因为你想写电路?太好了!

本节将指导你通过halo创建电路的过程。

Developer tools

The halo2 crate includes several utilities to help you design and implement your circuits.

Mock prover

halo2::dev::MockProver is a tool for debugging circuits, as well as cheaply verifying their correctness in unit tests. The private and public inputs to the circuit are constructed as would normally be done to create a proof, but MockProver::run instead creates an object that will test every constraint in the circuit directly. It returns granular error messages that indicate which specific constraint (if any) is not satisfied.

Circuit visualizations

The dev-graph feature flag exposes several helper methods for creating graphical representations of circuits.

halo2::dev::circuit_layout renders the circuit layout as a grid:

  • Columns are layed out from left to right as advice, instance, and fixed. The order of columns is otherwise without meaning.
    • Advice columns have a red background.
    • Instance columns have a white background.
    • Fixed columns have a blue background.
  • Regions are shown as labelled green boxes (overlaying the background colour). A region may appear as multiple boxes if some of its columns happen to not be adjacent.
  • Cells that have been assigned to by the circuit will be shaded in grey. If any cells are assigned to more than once (which is usually a mistake), they will be shaded darker than the surrounding cells.

halo2::dev::circuit_dot_graph builds a DOT graph string representing the given circuit, which can then be rendered witha variety of layout programs. The graph is built from calls to Layouter::namespace both within the circuit, and inside the gadgets and chips that it uses.

Cost estimator

The cost-model binary takes high-level parameters for a circuit design, and estimates the verification cost, as well as resulting proof size.

Usage: cargo run --example cost-model -- [OPTIONS] k

Positional arguments:
  k                       2^K bound on the number of rows.

Optional arguments:
  -h, --help              Print this message.
  -a, --advice R[,R..]    An advice column with the given rotations. May be repeated.
  -i, --instance R[,R..]  An instance column with the given rotations. May be repeated.
  -f, --fixed R[,R..]     A fixed column with the given rotations. May be repeated.
  -g, --gate-degree D     Maximum degree of the custom gates.
  -l, --lookup N,I,T      A lookup over N columns with max input degree I and max table degree T. May be repeated.
  -p, --permutation N     A permutation over N columns. May be repeated.

For example, to estimate the cost of a circuit with three advice columns and one fixed column (with various rotations), and a maximum gate degree of 4:

<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7777700000000001em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">c</span><span class="mord mathnormal">a</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal" style="margin-right:0.02778em;">or</span><span class="mord mathnormal">u</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord">−</span><span class="mord mathnormal">e</span><span class="mord mathnormal">x</span><span class="mord mathnormal">am</span><span class="mord mathnormal" style="margin-right:0.01968em;">pl</span><span class="mord mathnormal">ecos</span><span class="mord mathnormal">t</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">m</span><span class="mord mathnormal">o</span><span class="mord mathnormal">d</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">a</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">a</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">−</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord">411</span><span class="mord mathnormal" style="margin-right:0.13889em;">F</span><span class="mord mathnormal">ini</span><span class="mord mathnormal">s</span><span class="mord mathnormal">h</span><span class="mord mathnormal">e</span><span class="mord mathnormal">dd</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.03588em;">v</span><span class="mopen">[</span><span class="mord mathnormal">u</span><span class="mord mathnormal">n</span><span class="mord mathnormal">o</span><span class="mord mathnormal">pt</span><span class="mord mathnormal">imi</span><span class="mord mathnormal">ze</span><span class="mord mathnormal">d</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">d</span><span class="mord mathnormal">e</span><span class="mord mathnormal">b</span><span class="mord mathnormal" style="margin-right:0.03588em;">ug</span><span class="mord mathnormal">in</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mord mathnormal">o</span><span class="mclose">]</span><span class="mord mathnormal">t</span><span class="mord mathnormal">a</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">e</span><span class="mord mathnormal">t</span><span class="mopen">(</span><span class="mord mathnormal">s</span><span class="mclose">)</span><span class="mord mathnormal">in</span><span class="mord">0.03</span><span class="mord mathnormal">s</span><span class="mord mathnormal" style="margin-right:0.00773em;">R</span><span class="mord mathnormal">u</span><span class="mord mathnormal">nnin</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord">‘</span><span class="mord mathnormal">t</span><span class="mord mathnormal">a</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">e</span><span class="mord mathnormal">t</span><span class="mord">/</span><span class="mord mathnormal">d</span><span class="mord mathnormal">e</span><span class="mord mathnormal">b</span><span class="mord mathnormal" style="margin-right:0.03588em;">ug</span><span class="mord">/</span><span class="mord mathnormal">e</span><span class="mord mathnormal">x</span><span class="mord mathnormal">am</span><span class="mord mathnormal" style="margin-right:0.01968em;">pl</span><span class="mord mathnormal">es</span><span class="mord">/</span><span class="mord mathnormal">cos</span><span class="mord mathnormal">t</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">m</span><span class="mord mathnormal">o</span><span class="mord mathnormal">d</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">a</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">a</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">a</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">−</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.036108em;vertical-align:-0.286108em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord">411‘</span><span class="mord mathnormal" style="margin-right:0.07153em;">C</span><span class="mord mathnormal">i</span><span class="mord mathnormal">rc</span><span class="mord mathnormal">u</span><span class="mord mathnormal">i</span><span class="mord mathnormal">t</span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord">11</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">ma</span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.33610799999999996em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">d</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord">4</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">a</span><span class="mord mathnormal">d</span><span class="mord mathnormal" style="margin-right:0.03588em;">v</span><span class="mord mathnormal">i</span><span class="mord mathnormal">c</span><span class="mord"><span class="mord mathnormal">e</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">c</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord mathnormal">o</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">u</span><span class="mord mathnormal">mn</span><span class="mord mathnormal">s</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord">3</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">oo</span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mord mathnormal">u</span><span class="mord mathnormal">p</span><span class="mord mathnormal">s</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">p</span><span class="mord mathnormal" style="margin-right:0.02778em;">er</span><span class="mord mathnormal">m</span><span class="mord mathnormal">u</span><span class="mord mathnormal">t</span><span class="mord mathnormal">a</span><span class="mord mathnormal">t</span><span class="mord mathnormal">i</span><span class="mord mathnormal">o</span><span class="mord mathnormal">n</span><span class="mord mathnormal">s</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mopen">[</span><span class="mclose">]</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">co</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">u</span><span class="mord mathnormal">m</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.15139200000000003em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03588em;">q</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mord mathnormal">u</span><span class="mord mathnormal" style="margin-right:0.02778em;">er</span><span class="mord mathnormal">i</span><span class="mord mathnormal">es</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord">7</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">p</span><span class="mord mathnormal">o</span><span class="mord mathnormal">in</span><span class="mord"><span class="mord mathnormal">t</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">s</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord mathnormal">e</span><span class="mord mathnormal">t</span><span class="mord mathnormal">s</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord">3</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">es</span><span class="mord mathnormal">t</span><span class="mord mathnormal">ima</span><span class="mord mathnormal">t</span><span class="mord mathnormal" style="margin-right:0.02778em;">or</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord mathnormal" style="margin-right:0.05764em;">E</span><span class="mord mathnormal">s</span><span class="mord mathnormal">t</span><span class="mord mathnormal">ima</span><span class="mord mathnormal">t</span><span class="mord mathnormal" style="margin-right:0.02778em;">or</span><span class="mpunct">,</span></span><span class="mord mathnormal" style="margin-right:0.13889em;">P</span><span class="mord mathnormal">roo</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mord mathnormal">s</span><span class="mord mathnormal">i</span><span class="mord mathnormal">ze</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord">1440</span><span class="mord mathnormal">b</span><span class="mord mathnormal" style="margin-right:0.03588em;">y</span><span class="mord mathnormal">t</span><span class="mord mathnormal">es</span><span class="mord mathnormal" style="margin-right:0.22222em;">V</span><span class="mord mathnormal" style="margin-right:0.02778em;">er</span><span class="mord mathnormal">i</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mord mathnormal">i</span><span class="mord mathnormal">c</span><span class="mord mathnormal">a</span><span class="mord mathnormal">t</span><span class="mord mathnormal">i</span><span class="mord mathnormal">o</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal">a</span><span class="mord mathnormal" style="margin-right:0.01968em;">tl</span><span class="mord mathnormal">e</span><span class="mord mathnormal">a</span><span class="mord mathnormal">s</span><span class="mord mathnormal">t</span><span class="mord">81.689</span><span class="mord mathnormal">m</span><span class="mord mathnormal">s</span><span class="mord">‘‘‘</span></span></span></span>

A simple example

Let's start with a simple circuit, to introduce you to the common APIs and how they are used. The circuit will take a public input , and will prove knowledge of two private inputs and such that

Define instructions

Firstly, we need to define the instructions that our circuit will rely on. Instructions are the boundary between high-level gadgets and the low-level circuit operations. Instructions may be as coarse or as granular as desired, but in practice you want to strike a balance between an instruction being large enough to effectively optimize its implementation, and small enough that it is meaningfully reusable.

For our circuit, we will use three instructions:

  • Load a private number into the circuit.
  • Multiply two numbers.
  • Expose a number as a public input to the circuit.

We also need a type for a variable representing a number. Instruction interfaces provide associated types for their inputs and outputs, to allow the implementations to represent these in a way that makes the most sense for their optimization goals.

{{#include ../../../examples/simple-example.rs:instructions}}

Define a chip implementation

For our circuit, we will build a chip that provides the above numeric instructions for a finite field.

{{#include ../../../examples/simple-example.rs:chip}}

Every chip needs to implement the Chip trait. This defines the properties of the chip that a Layouter may rely on when synthesizing a circuit, as well as enabling any initial state that the chip requires to be loaded into the circuit.

{{#include ../../../examples/simple-example.rs:chip-impl}}

Configure the chip

The chip needs to be configured with the columns, permutations, and gates that will be required to implement all of the desired instructions.

{{#include ../../../examples/simple-example.rs:chip-config}}

Implement chip traits

{{#include ../../../examples/simple-example.rs:instructions-impl}}

Build the circuit

Now that we have the instructions we need, and a chip that implements them, we can finally build our circuit!

{{#include ../../../examples/simple-example.rs:circuit}}

Testing the circuit

halo2::dev::MockProver can be used to test that the circuit is working correctly. The private and public inputs to the circuit are constructed as we will do to create a proof, but by passing them to MockProver::run we get an object that can test every constraint in the circuit, and tell us exactly what is failing (if anything).

{{#include ../../../examples/simple-example.rs:test-circuit}}

Full example

You can find the source code for this example here.

Lookup tables

In normal programs, you can trade memory for CPU to improve performance, by pre-computing and storing lookup tables for some part of the computation. We can do the same thing in halo2 circuits!

A lookup table can be thought of as enforcing a relation between variables, where the relation is expressed as a table. Assuming we have only one lookup argument in our constraint system, the total size of tables is constrained by the size of the circuit: each table entry costs one row, and it also costs one row to do each lookup.

TODO

Gadgets

Tips and tricks

This section contains various ideas and snippets that you might find useful while writing halo2 circuits.

Small range constraints

A common constraint used in R1CS circuits is the boolean constraint: . This constraint can only be satisfied by or .

In halo2 circuits, you can similarly constrain a cell to have one of a small set of values. For example, to constrain to the range , you would create a gate of the form:

while to constraint to be either 7 or 13, you would use:

The underlying principle here is that we create a polynomial constraint with roots at each value in the set of possible values we want to allow. In R1CS circuits, the maximum supported polynomial degree is 2 (due to all constraints being of the form ). In halo2 circuits, you can use arbitrary-degree polynomials - with the proviso that higher-degree constraints are more expensive to use.

Note that the roots don't have to be constants; for example will constrain to be equal to one of where the latter can be arbitrary polynomials, as long as the whole expression stays within the maximum degree bound.

Small set interpolation

We can use Lagrange interpolation to create a polynomial constraint that maps for small sets of .

For instance, say we want to map a 2-bit value to a "spread" version interleaved with zeros. We first precompute the evaluations at each point:

Then, we construct the Lagrange basis polynomial for each point using the identity: where is the number of data points. ( in our example above.)

Recall that the Lagrange basis polynomial evaluates to at and at all other

Continuing our example, we get four Lagrange basis polynomials:

Our polynomial constraint is then

Design

Note on Language

We use slightly different language than others to describe PLONK concepts. Here's the overview:

  1. We like to think of PLONK-like arguments as tables, where each column corresponds to a "wire". We refer to entries in this table as "cells".
  2. We like to call "selector polynomials" and so on "fixed columns" instead. We then refer specifically to a "selector constraint" when a cell in a fixed column is being used to control whether a particular constraint is enabled in that row.
  3. We call the other polynomials "advice columns" usually, when they're populated by the prover.
  4. We use the term "rule" to refer to a "gate" like
    • TODO: Check how consistent we are with this, and update the code and docs to match.

Proving system

The Halo 2 proving system can be broken down into five stages:

  1. Commit to polynomials encoding the main components of the circuit:
    • Cell assignments.
    • Permuted values and products for each lookup argument.
    • Equality constraint permutations.
  2. Construct the vanishing argument to constrain all circuit relations to zero:
    • Standard and custom gates.
    • Lookup argument rules.
    • Equality constraint permutation rules.
  3. Evaluate the above polynomials at all necessary points:
    • All relative rotations used by custom gates across all columns.
    • Vanishing argument pieces.
  4. Construct the multipoint opening argument to check that all evaluations are consistent with their respective commitments.
  5. Run the inner product argument to create a polynomial commitment opening proof for the multipoint opening argument polynomial.

These stages are presented in turn across this section of the book.

Example

To aid our explanations, we will at times refer to the following example constraint system:

  • Four advice columns .
  • One fixed column .
  • Three custom gates:

tl;dr

The table below provides a (probably too) succinct description of the Halo 2 protocol. This description will likely be replaced by the Halo 2 paper and security proof, but for now serves as a summary of the following sub-sections.

ProverVerifier
Checks
Constructs multipoint opening poly

Then the prover and verifier:

  • Construct as a linear combination of and using powers of ;
  • Construct as the equivalent linear combination of and ; and
  • Perform

TODO: Write up protocol components that provide zero-knowledge.

查找(Lookup)论据

halo2实现任意集合的数据查找,相比Plookup简单。

语言(Language)说明

除了 语言的一般说明:

  • 多项式(针对置换论据的大乘积论据多项式)称为“置换乘积”列。

技术描述

为了解释简单,我们先描述一个忽略零知识证明的论据描述的简单版本。

查找可以表示成 行表(编号从0开始)的“子集”。列分别是“子集”和“全集”。

“子集”论据保证列中的元素都在 列中。这意味着,列中多个位置的元素对应着列中同一位置的元素,并且列中的某些元素可以不出现在列的任何位置上。

  • 列并不一定是固定的。也就是说,我们可以支持固定元素的查找或者动态查找(后者采用advice列)。
  • 列中的元素可以重复。如果列中的元素个数不正好是的话,可以用列中任意元素进行扩展。
    • 或者我们可以增加一个“查找选择子”,控制在列中的哪些元素参与查找。采用这种方法可以替换下述公式中的 。如果一个元素不需要查找,用替换

假设 是拉格朗日基多项式,在行多项式为1,其他行为0。

列的置换开始。假设它们的置换分别为列。我们可以通过置换论据约束它们之间的置换关系:

也就是说,在除以0不发生的情况下,对所有的满足:

这个版本的论据证明列是列的置换,但是并没有指明具体的置换关系。 是独立因子。采用这两个因子,可以将两个置换论据组合在一起,不需要担心相互干扰。

这些置换的目的是让证明者提供的列满足一定的条件:

  1. 列中相同的元素位置靠在一起。这可以通过某种排序算法实现。重要的是,相同的元素在列中挨在一起,并且列是列的置换。
  2. 列中挨在一起的相同元素的第一个元素存在于列中。除去这个限制外,列是列的一个任意置换。

现在我们通过如下的规则限制 或者

除此之外,我们通过如下的规则限制

由于第二个规则,第一个规则中的( 这一项在行没有效果,尽管 “能反转”。

这些约束规则一起有效的限制了列(也就是列)中的每个元素都存在于 列中(也就是列)。

加入零知识

为了在PLONK算法为基础的证明系统中加入零知识,我们需要在每列的最后加入个随机元素。这些需要对查找论据进行调整,因为这些随机的元素并不满足之前的约束。

我们限制有效的行数为。我们增加两个选择子:

  • 在最后 行设置为1,其他行设置为0;
  • 只在行设置为1,其他行设置为0 (也就是说,它设置在有效行和盲化行的交界处)。

我们将之前的规则限制在有效行上:

行的限制规则保持不变:

因为我们不能再依赖在 点的环绕保证为1,相反我们要约束 为1。这里有个难点:如果在任意 或者 为0的话,置换论据可能不成立。虽然这种情况在 的取值下概率可以忽略,但是,对于完美零知识和完备性来说是个障碍(攻击者可以构造这样的情况)。

确保完美的完备性和零知识,我们允许为0或者1:

如果在某些 上为0,我们可以在范围设置,满足上述的约束。

注意的是,挑战因子 是在列(以及列)承诺后生成的,证明者无法伪造为0的情况。因为这种情况的概率可以忽略,可行性不受影响。

开销

  • 原始列和固定列。
  • 置换函数
  • 两个置换列。
  • 约束方程(门)的阶都不高。

泛化

halo2的查找论据实现实现了上述技术的泛化:

  • 列扩展为多列,这些列之间通过随机挑战因子进行组合。列还是单列。
    • 列的各列承诺可以提前计算。这样在挑战因子确定后,利用Pedersen承诺的同态性质,可以很简便的组合。
    • 列可以是采用相对引用的任意多项式表达式。这些可以替换到约束规则中去,受制于最大的阶。这样可能可以省去一个或者多个advice列。
  • 这样的话,任意关系的查找论据可以通过子集论据实现。也就是说,为了约束,考虑的子集(通过前面的方法),并且检查关系成立
    • 如果代表一个函数,同样需要检查输入是否在域中。这是我们想要的,经常会省去额外的范围检查。In the case where represents a function, this implicitly also checks that the inputs are in the domain. This is typically what we want, and often saves an additional range check.
  • 我们可以在同一个电路中支持多表。利用标示列将多个表组合成一张表。
    • 标示列可以和之前提到的“查找选择子”合并。

这些泛化和Plookup论文的第4和第5节中的技术类似。和Plookup的区别是子集论据。相关技术,子集论据也适用;举个例子,Plookup论文的第5节中的优化范围检查技术同样可以用在子集论据中。

Permutation argument

Given that gates in halo2 circuits operate "locally" (on cells in the current row or defined relative rows), it is common to need to copy a value from some arbitrary cell into the current row for use in a gate. This is performed with an equality constraint, which enforces that the source and destination cells contain the same value.

We implement these equality constraints by constructing a permutation that represents the constraints, and then using a permutation argument within the proof to enforce them.

Notation

A permutation is a one-to-one and onto mapping of a set onto itself. A permutation can be factored uniquely into a composition of cycles (up to ordering of cycles, and rotation of each cycle).

We sometimes use cycle notation to write permutations. Let denote a cycle where maps to maps to and maps to (with the obvious generalization to arbitrary-sized cycles). Writing two or more cycles next to each other denotes a composition of the corresponding permutations. For example, denotes the permutation that maps to to to and to

Constructing the permutation

Goal

We want to construct a permutation in which each subset of variables that are in a equality-constraint set form a cycle. For example, suppose that we have a circuit that defines the following equality constraints:

From this we have the equality-constraint sets and We want to construct the permutation:

which defines the mapping of to

Algorithm

We need to keep track of the set of cycles, which is a set of disjoint sets. Efficient data structures for this problem are known; for the sake of simplicity we choose one that is not asymptotically optimal but is easy to implement.

We represent the current state as:

  • an array for the permutation itself;
  • an auxiliary array that keeps track of a distinguished element of each cycle;
  • another array that keeps track of the size of each cycle.

We have the invariant that for each element in a given cycle points to the same element This allows us to quickly decide whether two given elements and are in the same cycle, by checking whether Also, gives the size of the cycle containing (This is guaranteed only for not for )

The algorithm starts with a representation of the identity permutation: for all we set and

To add an equality constraint :

  1. Check whether and are already in the same cycle, i.e. whether If so, there is nothing to do.
  2. Otherwise, and belong to different cycles. Make the larger cycle and the smaller one, by swapping them iff
  3. Set
  4. Following the mapping around the right (smaller) cycle, for each element set
  5. Splice the smaller cycle into the larger one by swapping with

For example, given two disjoint cycles and :

A +---> B
^       +
|       |
+       v
D <---+ C       E +---> F
                ^       +
                |       |
                +       v
                H <---+ G

After adding constraint the above algorithm produces the cycle:

A +---> B +-------------+
^                       |
|                       |
+                       v
D <---+ C <---+ E       F
                ^       +
                |       |
                +       v
                H <---+ G

Broken alternatives

If we did not check whether and were already in the same cycle, then we could end up undoing an equality constraint. For example, if we have the following constraints:

and we tried to implement adding an equality constraint just using step 5 of the above algorithm, then we would end up constructing the cycle rather than the correct

Argument specification

We need to check a permutation of cells in columns, represented in Lagrange basis by polynomials

We will label each cell in those columns with a unique element of

Suppose that we have a permutation on these labels, in which the cycles correspond to equality-constraint sets.

If we consider the set of pairs , then the values within each cycle are equal if and only if permuting the label in each pair by yields the same set:

An example for a cycle (A B C D). The set before permuting the labels is {(A, 7), (B, 7), (C, 7), (D, 7)}, and the set after is {(D, 7), (A, 7), (B, 7), (C, 7)} which is the same. If one of the 7s is replaced by 3, then the set after permuting labels is not the same.

Since the labels are distinct, set equality is the same as multiset equality, which we can check using a product argument.

Let be a root of unity and let be a root of unity, where with odd and We will use as the label for the cell in the th row of the th column of the permutation argument.

We represent by a vector of polynomials such that

Notice that the identity permutation can be represented by the vector of polynomials such that

We will use a challenge to compress each pair to Just as in the product argument we used for lookups, we also use a challenge to randomize each term of the product.

Now given our permutation represented by over columns represented by we want to ensure that:

Here represents the unpermuted pair, and represents the permuted pair.

Let be such that and for :

Then it is sufficient to enforce the rules:

This assumes that the number of columns is such that the polynomial in the first rule above fits within the degree bound of the PLONK configuration. We will see below how to handle a larger number of columns.

The optimization used to obtain the simple representation of the identity permutation was suggested by Vitalik Buterin for PLONK, and is described at the end of section 8 of the PLONK paper. Note that the are all distinct quadratic non-residues, provided that the number of columns that are enabled for equality is no more than , which always holds in practice for the curves used in Halo 2.

Zero-knowledge adjustment

Similarly to the lookup argument, we need an adjustment to the above argument to account for the last rows of each column being filled with random values.

We limit the number of usable rows to We add two selectors, defined in the same way as for the lookup argument:

  • is set to on the last rows, and elsewhere;
  • is set to only on row and elsewhere (i.e. it is set on the row in between the usable rows and the blinding rows).

We enable the product rule from above only for the usable rows:

The rule that is enabled on row remains the same:

Since we can no longer rely on the wraparound to ensure that each product becomes again at we would instead need to constrain This raises the same problem that was described for the lookup argument. So we allow to be either zero or one:

which gives perfect completeness and zero knowledge.

Spanning a large number of columns

The halo2 implementation does not in practice limit the number of columns for which equality constraints can be enabled. Therefore, it must solve the problem that the above approach might yield a product rule with a polynomial that exceeds the PLONK configuration's degree bound. The degree bound could be raised, but this would be inefficient if no other rules require a larger degree.

Instead, we split the product across sets of columns, using product columns and we use another rule to copy the product from the end of one column set to the beginning of the next.

That is, for we have:

For simplicity this is written assuming that the number of columns enabled for equality constraints is a multiple of ; if not then the products for the last column set will have fewer than terms.

For the first column set we have:

For each subsequent column set, we use the following rule to copy to the start of the next column set, :

For the last column set, we allow to be either zero or one:

which gives perfect completeness and zero knowledge as before.

Circuit commitments

Committing to the circuit assignments

At the start of proof creation, the prover has a table of cell assignments that it claims satisfy the constraint system. The table has rows, and is broken into advice, instance, and fixed columns. We define as the assignment in the th row of the th fixed column. Without loss of generality, we'll similarly define to represent the advice and instance assignments.

We separate fixed columns here because they are provided by the verifier, whereas the advice and instance columns are provided by the prover. In practice, the commitments to instance and fixed columns are computed by both the prover and verifier, and only the advice commitments are stored in the proof.

To commit to these assignments, we construct Lagrange polynomials of degree for each column, over an evaluation domain of size (where is the th primitive root of unity):

  • interpolates such that .
  • interpolates such that .

We then create a blinding commitment to the polynomial for each column:

is constructed as part of key generation, using a blinding factor of . is constructed by the prover and sent to the verifier.

Committing to the lookup permutations

The verifier starts by sampling , which is used to keep individual columns within lookups independent. Then, the prover commits to the permutations for each lookup as follows:

  • Given a lookup with input column polynomials and table column polynomials , the prover constructs two compressed polynomials

  • The prover then permutes and according to the rules of the lookup argument, obtaining and .

The prover creates blinding commitments for all of the lookups

and sends them to the verifier.

After the verifier receives , , and , it samples challenges and that will be used in the permutation argument and the remainder of the lookup argument below. (These challenges can be reused because the arguments are independent.)

Committing to the equality constraint permutation

Let be the number of columns that are enabled for equality constraints.

Let be the maximum number of columns that can accomodated by a column set without exceeding the PLONK configuration's polynomial degree bound.

Let be the number of “usable” rows as defined in the Permutation argument section.

Let

The prover constructs a vector of length such that for each column set and each row

The prover then computes a running product of , starting at , and a vector of polynomials that each have a Lagrange basis representation corresponding to a -sized slice of this running product, as described in the Permutation argument section.

The prover creates blinding commitments to each polynomial:

and sends them to the verifier.

Committing to the lookup permutation product columns

In addition to committing to the individual permuted lookups, for each lookup, the prover needs to commit to the permutation product column:

  • The prover constructs a vector :

  • The prover constructs a polynomial which has a Lagrange basis representation corresponding to a running product of , starting at .

and are used to combine the permutation arguments for and while keeping them independent. The important thing here is that the verifier samples and after the prover has created , , and (and thus committed to all the cell values used in lookup columns, as well as and for each lookup).

As before, the prover creates blinding commitments to each polynomial:

and sends them to the verifier.

Vanishing argument

Having committed to the circuit assignments, the prover now needs to demonstrate that the various circuit relations are satisfied:

  • The custom gates, represented by polynomials .
  • The rules of the lookup arguments.
  • The rules of the equality constraint permutations.

Each of these relations is represented as a polynomial of degree (the maximum degree of any of the relations) with respect to the circuit columns. Given that the degree of the assignment polynomials for each column is , the relation polynomials have degree with respect to .

In our example, these would be the gate polynomials, of degree :

A relation is satisfied if its polynomial is equal to zero. One way to demonstrate this is to divide each polynomial relation by the vanishing polynomial , which is the lowest-degree monomial that has roots at every . If relation's polynomial is perfectly divisible by , it is equal to zero over the domain (as desired).

This simple construction would require a polynomial commitment per relation. Instead, we commit to all of the circuit relations simultaneously: the verifier samples , and then the prover constructs the quotient polynomial

where the numerator is a random (the prover commits to the cell assignments before the verifier samples ) linear combination of the circuit relations.

  • If the numerator polynomial (in formal indeterminate ) is perfectly divisible by , then with high probability all relations are satisfied.
  • Conversely, if at least one relation is not satisfied, then with high probability will not equal the evaluation of the numerator at . In this case, the numerator polynomial would not be perfectly divisible by .

Committing to

has degree (because the divisor has degree ). However, the polynomial commitment scheme we use for Halo 2 only supports committing to polynomials of degree (which is the maximum degree that the rest of the protocol needs to commit to). Instead of increasing the cost of the polynomial commitment scheme, the prover split into pieces of degree

and produces blinding commitments to each piece

Evaluating the polynomials

At this point, all properties of the circuit have been committed to. The verifier now wants to see if the prover committed to the correct polynomial. The verifier samples , and the prover produces the purported evaluations of the various polynomials at , for all the relative offsets used in the circuit, as well as .

In our example, this would be:

  • ,
  • ,
  • , ...,

The verifier checks that these evaluations satisfy the form of :

Now content that the evaluations collectively satisfy the gate constraints, the verifier needs to check that the evaluations themselves are consistent with the original circuit commitments, as well as . To implement this efficiently, we use a multipoint opening argument.

Multipoint opening argument

Consider the commitments to polynomials . Let's say that and were queried at the point , while and were queried at both points and . (Here, is the primitive root of unity in the multiplicative subgroup over which we constructed the polynomials).

To open these commitments, we could create a polynomial for each point that we queried at (corresponding to each relative rotation used in the circuit). But this would not be efficient in the circuit; for example, would appear in multiple polynomials.

Instead, we can group the commitments by the sets of points at which they were queried:

For each of these groups, we combine them into a polynomial set, and create a single for that set, which we open at each rotation.

Optimization steps

The multipoint opening optimization takes as input:

  • A random sampled by the verifier, at which we evaluate .
  • Evaluations of each polynomial at each point of interest, provided by the prover:

These are the outputs of the vanishing argument.

The multipoint opening optimization proceeds as such:

  1. Sample random , to keep linearly independent.

  2. Accumulate polynomials and their corresponding evaluations according to the point set at which they were queried: q_polys: q_eval_sets:

            [
                [a(x) + x_1 b(x)],
                [
                    c(x) + x_1 d(x),
                    c(\omega x) + x_1 d(\omega x)
                ]
            ]
    

    NB: q_eval_sets is a vector of sets of evaluations, where the outer vector goes over the point sets, and the inner vector goes over the points in each set.

  3. Interpolate each set of values in q_eval_sets: r_polys:

  4. Construct f_polys which check the correctness of q_polys: f_polys

    If , then should be a polynomial. If and then should be a polynomial.

  5. Sample random to keep the f_polys linearly independent.

  6. Construct .

  7. Sample random , at which we evaluate :

  8. Sample random to keep and q_polys linearly independent.

  9. Construct final_poly, which is the polynomial we commit to in the inner product argument.

Inner product argument

Halo 2 uses a polynomial commitment scheme for which we can create polynomial commitment opening proofs, based around the Inner Product Argument.

TODO: Explain Halo 2's variant of the IPA.

It is very similar to from Appendix A.2 of BCMS20. See this comparison for details.

Comparison to other work

BCMS20 Appendix A.2

Appendix A.2 of BCMS20 describes a polynomial commitment scheme that is similar to the one described in BGH19 (BCMS20 being a generalization of the original Halo paper). Halo 2 builds on both of these works, and thus itself uses a polynomial commitment scheme that is very similar to the one in BCMS20.

The following table provides a mapping between the variable names in BCMS20, and the equivalent objects in Halo 2 (which builds on the nomenclature from the Halo paper):

BCMS20Halo 2
msm or
challenge_i
s_poly
s_poly_blind
s_poly_commitment
blind /

Halo 2's polynomial commitment scheme differs from Appendix A.2 of BCMS20 in two ways:

  1. Step 8 of the algorithm computes a "non-hiding" commitment prior to the inner product argument, which opens to the same value as but is a commitment to a randomly-drawn polynomial. The remainder of the protocol involves no blinding. By contrast, in Halo 2 we blind every single commitment that we make (even for instance and fixed polynomials, though using a blinding factor of 1 for the fixed polynomials); this makes the protocol simpler to reason about. As a consequence of this, the verifier needs to handle the cumulative blinding factor at the end of the protocol, and so there is no need to derive an equivalent to at the start of the protocol.

    • is also an input to the random oracle for ; in Halo 2 we utilize a transcript that has already committed to the equivalent components of prior to sampling .
  2. The subroutine (Figure 2 of BCMS20) computes the initial group element by adding , which requires two scalar multiplications. Instead, we subtract from the original commitment , so that we're effectively opening the polynomial at the point to the value zero. The computation is more efficient in the context of recursion because is a fixed base (so we can use lookup tables).

Protocol Description

Preliminaries

We take as our security parameter, and unless explicitly noted all algorithms and adversaries are probabilistic (interactive) Turing machines that run in polynomial time in this security parameter. We use to denote a function that is negligible in .

Cryptographic Groups

We let denote a cyclic group of prime order . The identity of a group is written as . We refer to the scalars of elements in as elements in a scalar field of size . Group elements are written in capital letters while scalars are written in lowercase or Greek letters. Vectors of scalars or group elements are written in boldface, i.e. and . Group operations are written additively and the multiplication of a group element by a scalar is written .

We will often use the notation to describe the inner product of two like-length vectors of scalars . We also use this notation to represent the linear combination of group elements such as with , computed in practice by a multiscalar multiplication.

We use to describe a vector of length that contains only zeroes in .

Discrete Log Relation Problem. The advantage metric is defined with respect the following game.

Given an -length vector of group elements, the discrete log relation problem asks for such that and yet , which we refer to as a non-trivial discrete log relation. The hardness of this problem is tightly implied by the hardness of the discrete log problem in the group as shown in Lemma 3 of [JT20]. Formally, we use the game defined above to capture this problem.

Interactive Proofs

Interactive proofs are a triple of algorithms . The algorithm produces as its output some public parameters commonly refered to by . The prover and verifier are interactive machines (with access to ) and we denote by an algorithm that executes a two-party protocol between them on inputs . The output of this protocol, a transcript of their interaction, contains all of the messages sent between and . At the end of the protocol, the verifier outputs a decision bit.

Zero knowledge Arguments of Knowledge

Proofs of knowledge are interactive proofs where the prover aims to convince the verifier that they know a witness such that for a statement and polynomial-time decidable relation . We will work with arguments of knowledge which assume computationally-bounded provers.

We will analyze arguments of knowledge through the lens of four security notions.

  • Completeness: If the prover possesses a valid witness, can they always convince the verifier? It is useful to understand this property as it can have implications for the other security notions.
  • Soundness: Can a cheating prover falsely convince the verifier of the correctness of a statement that is not actually correct? We refer to the probability that a cheating prover can falsely convince the verifier as the soundness error.
  • Knowledge soundness: When the verifier is convinced the statement is correct, does the prover actually possess ("know") a valid witness? We refer to the probability that a cheating prover falsely convinces the verifier of this knowledge as the knowledge error.
  • Zero knowledge: Does the prover learn anything besides that which can be inferred from the correctness of the statement and the prover's knowledge of a valid witness?

First, we will visit the simple definition of completeness.

Perfect Completeness. An interactive argument has perfect completeness if for all polynomial-time decidable relations and for all non-uniform polynomial-time adversaries

Soundness

Complicating our analysis is that although our protocol is described as an interactive argument, it is realized in practice as a non-interactive argument through the use of the Fiat-Shamir transformation.

Public coin. We say that an interactive argument is public coin when all of the messages sent by the verifier are each sampled with fresh randomness.

Fiat-Shamir transformation. In this transformation an interactive, public coin argument can be made non-interactive in the random oracle model by replacing the verifier algorithm with a cryptographically strong hash function that produces sufficiently random looking output.

This transformation means that in the concrete protocol a cheating prover can easily "rewind" the verifier by forking the transcript and sending new messages to the verifier. Studying the concrete security of our construction after applying this transformation is important. Fortunately, we are able to follow a framework of analysis by Ghoshal and Tessaro ([GT20]) that has been applied to constructions similar to ours.

We will study our protocol through the notion of state-restoration soundness. In this model the (cheating) prover is allowed to rewind the verifier to any previous state it was in. The prover wins if they are able to produce an accepting transcript.

State-Restoration Soundness. Let be an interactive argument with verifier challenges and let the th challenge be sampled from . The advantage metric of a state restoration prover is defined with respect to the following game.

As shown in [GT20] (Theorem 1) state restoration soundness is tightly related to soundness after applying the Fiat-Shamir transformation.

Knowledge Soundness

We will show that our protocol satisfies a strengthened notion of knowledge soundness known as witness extended emulation. Informally, this notion states that for any successful prover algorithm there exists an efficient emulator that can extract a witness from it by rewinding it and supplying it with fresh randomness.

However, we must slightly adjust our definition of witness extended emulation to account for the fact that our provers are state restoration provers and can rewind the verifier. Further, to avoid the need for rewinding the state restoration prover during witness extraction we study our protocol in the algebraic group model.

Algebraic Group Model (AGM). An adversary is said to be algebraic if whenever it outputs a group element it also outputs a representation such that where is the vector of group elements that has seen so far. Notationally, we write to describe a group element enhanced with this representation. We also write to identify the component of the representation of that corresponds with . In other words,

The algebraic group model allows us to perform so-called "online" extraction for some protocols: the extractor can obtain the witness from the representations themselves for a single (accepting) transcript.

State Restoration Witness Extended Emulation Let be an interactive argument for relation with challenges. We define for all non-uniform algebraic provers , extractors , and computationally unbounded distinguishers the advantage metric is defined with the respect to the following games.

Zero Knowledge

We say that an argument of knowledge is zero knowledge if the verifier also does not learn anything from their interaction besides that which can be learned from the existence of a valid . More formally,

Perfect Special Honest-Verifier Zero Knowledge. A public coin interactive argument has perfect special honest-verifier zero knowledge (PSHVZK) if for all polynomial-time decidable relations and for all and for all non-uniform polynomial-time adversaries there exists a probabilistic polynomial-time simulator such that where is the internal randomness of the verifier.

In this (common) definition of zero-knowledge the verifier is expected to act "honestly" and send challenges that correspond only with their internal randomness; they cannot adaptively respond to the prover based on the prover's messages. We use a strengthened form of this definition that forces the simulator to output a transcript with the same (adversarially provided) challenges that the verifier algorithm sends to the prover.

Protocol

Let be a primitive root of unity forming the domain with the vanishing polynomial over this domain. Let be positive integers. We present an interactive argument for the relation where are (multivariate) polynomials with degree in and has degree in .

returns .

For all :

  • Let be the exhaustive set of integers (modulo ) such that appears as a term in .
  • Let be a list of distinct sets of integers containing and the set .
  • Let when .

Let denote the size of , and let denote the size of every without loss of generality.

In the following protocol, we take it for granted that each polynomial is defined such that blinding factors are freshly sampled by the prover and are each present as an evaluation of over the domain .

  1. and proceed in the following rounds of interaction, where in round (starting at )
  • sets
  • sends a hiding commitment where are the coefficients of the univariate polynomial and is some random, independently sampled blinding factor elided for exposition.
  • responds with a challenge .
  1. and set .
  2. sends a commitment where are the coefficients of a randomly sampled univariate polynomial of degree .
  3. computes univariate polynomial of degree .
  4. computes at most degree polynomials such that .
  5. sends commitments for all where denotes the vector of coefficients for .
  6. responds with challenge and computes .
  7. sets .
  8. sends and for all sends such that for all .
  9. For all and set to be the lowest degree univariate polynomial defined such that for all .
  10. responds with challenges and initializes .
  • Starting at and ending at sets .
  • finally sets .
  1. initializes .
  • Starting at and ending at sets .
  • finally sets .
  1. and initialize .
  • Starting at and ending at and set .
  • Finally and set and where is computed by as using the values provided by .
  1. sends where defines the coefficients of the polynomial
  2. responds with challenge .
  3. sends such that for all .
  4. responds with challenge .
  5. and set and
  6. sets .
  7. samples a random polynomial of degree with a root at and sends a commitment where defines the coefficients of .
  8. responds with challenges .
  9. and set .
  10. sets .
  11. Initialize as the coefficients of and and . and will interact in the following rounds, where in the th round starting in round and ending in round :
  • sends and .
  • responds with challenge .
  • and set and .
  • sets .
  1. sends and synthetic blinding factor .
  2. accepts only if .

Implementation

Halo 2 proofs

Proofs as opaque byte streams

In proving system implementations like bellman, there is a concrete Proof struct that encapsulates the proof data, is returned by a prover, and can be passed to a verifier.

halo2 does not contain any proof-like structures, for several reasons:

  • The Proof structures would contain vectors of (vectors of) curve points and scalars. This complicates serialization/deserialization of proofs because the lengths of these vectors depend on the configuration of the circuit. However, we didn't want to encode the lengths of vectors inside of proofs, because at runtime the circuit is fixed, and thus so are the proof sizes.
  • It's easy to accidentally put stuff into a Proof structure that isn't also placed in the transcript, which is a hazard when developing and implementing a proving system.
  • We needed to be able to create multiple PLONK proofs at the same time; these proofs share many different substructures when they are for the same circuit.

Instead, halo2 treats proof objects as opaque byte streams. Creation and consumption of these byte streams happens via the transcript:

  • The TranscriptWrite trait represents something that we can write proof components to (at proving time).
  • The TranscriptRead trait represents something that we can read proof components from (at verifying time).

Crucially, implementations of TranscriptWrite are responsible for simultaneously writing to some std::io::Write buffer at the same time that they hash things into the transcript, and similarly for TranscriptRead/std::io::Read.

As a bonus, treating proofs as opaque byte streams ensures that verification accounts for the cost of deserialization, which isn't negligible due to point compression.

Proof encoding

A Halo 2 proof, constructed over a curve , is encoded as a stream of:

  • Points ) (for commitments to polynomials), and
  • Scalars ) (for evaluations of polynomials, and blinding values).

For the Pallas and Vesta curves, both points and scalars have 32-byte encodings, meaning that proofs are always a multiple of 32 bytes.

The halo2 crate supports proving multiple instances of a circuit simultaneously, in order to share common proof components and protocol logic.

In the encoding description below, we will use the following circuit-specific constants:

  • - the size parameter of the circuit (which has rows).
  • - the number of advice columns.
  • - the number of fixed columns.
  • - the number of instance columns.
  • - the number of lookup arguments.
  • - the number of permutation arguments.
  • - the number of columns involved in permutation argument .
  • - the maximum degree for the quotient polynomial.
  • - the number of advice column queries.
  • - the number of fixed column queries.
  • - the number of instance column queries.
  • - the number of instances of the circuit that are being proven simultaneously.

As the proof encoding directly follows the transcript, we can break the encoding into sections matching the Halo 2 protocol:

  • PLONK commitments:

    • points (repeated times).
    • points (repeated times).
    • points (repeated times).
    • points (repeated times).
  • Vanishing argument:

    • points.
    • scalars (repeated times).
    • scalars (repeated times).
    • scalars.
    • scalars.
  • PLONK evaluations:

    • scalars (repeated times).
    • scalars (repeated times).
  • Multiopening argument:

    • 1 point.
    • 1 scalar per set of points in the multiopening argument.
  • Polynomial commitment scheme:

    • points.
    • scalars.

Fields

The Pasta curves that we use in halo2 are designed to be highly 2-adic, meaning that a large multiplicative subgroup exists in each field. That is, we can write with odd. For both Pallas and Vesta, ; this helps to simplify the field implementations.

Sarkar square-root algorithm (table-based variant)

We use a technique from Sarkar2020 to compute square roots in halo2. The intuition behind the algorithm is that we can split the task into computing square roots in each multiplicative subgroup.

Suppose we want to find the square root of modulo one of the Pasta primes , where is a non-zero square in . We define a root of unity where is a non-square in , and precompute the following tables:

Let . We can then define as an element of the multiplicative subgroup.

Let

i = 0, 1

Using , we lookup such that

Define

i = 2

Lookup s.t.

Define

i = 3

Lookup s.t.

Define

Final result

Lookup such that

Let .

We can now write

Squaring the RHS, we observe that Therefore, the square root of is ; the first part we computed earlier, and the second part can be computed with three multiplications using lookups in .

Gadgets

In this section we document some example gadgets and chip designs that are suitable for Halo 2.

Neither these gadgets, nor their implementations, have been reviewed, and they should not be used in production.

SHA-256

Specification

SHA-256 is specified in NIST FIPS PUB 180-4.

Unlike the specification, we use for addition modulo , and for field addition. is used for XOR.

Gadget interface

SHA-256 maintains state in eight 32-bit variables. It processes input as 512-bit blocks, but internally splits these blocks into 32-bit chunks. We therefore designed the SHA-256 gadget to consume input in 32-bit chunks.

Chip instructions

The SHA-256 gadget requires a chip with the following instructions:


#![allow(unused)]
fn main() {
extern crate halo2;
use halo2::plonk::Error;
use std::fmt;

trait Chip: Sized {}
trait Layouter<C: Chip> {}
const BLOCK_SIZE: usize = 16;
const DIGEST_SIZE: usize = 8;

pub trait Sha256Instructions: Chip {
    /// Variable representing the SHA-256 internal state.
    type State: Clone + fmt::Debug;
    /// Variable representing a 32-bit word of the input block to the SHA-256 compression
    /// function.
    type BlockWord: Copy + fmt::Debug;

    /// Places the SHA-256 IV in the circuit, returning the initial state variable.
    fn initialization_vector(layouter: &mut impl Layouter<Self>) -> Result<Self::State, Error>;

    /// Starting from the given initial state, processes a block of input and returns the
    /// final state.
    fn compress(
        layouter: &mut impl Layouter<Self>,
        initial_state: &Self::State,
        input: [Self::BlockWord; BLOCK_SIZE],
    ) -> Result<Self::State, Error>;

    /// Converts the given state into a message digest.
    fn digest(
        layouter: &mut impl Layouter<Self>,
        state: &Self::State,
    ) -> Result<[Self::BlockWord; DIGEST_SIZE], Error>;
}
}

TODO: Add instruction for computing padding.

This set of instructions was chosen to strike a balance between the reusability of the instructions, and the scope for chips to internally optimise them. In particular, we considered splitting the compression function into its constituent parts (Ch, Maj etc), and providing a compression function gadget that implemented the round logic. However, this would prevent chips from using relative references between the various parts of a compression round. Having an instruction that implements all compression rounds is also similar to the Intel SHA extensions, which provide an instruction that performs multiple compression rounds.

16-bit table chip for SHA-256

This chip implementation is based around a single 16-bit lookup table. It requires a minimum of circuit rows, and is therefore suitable for use in larger circuits.

We target a maximum constraint degree of . That will allow us to handle constraining carries and "small pieces" to a range of up to in one row.

Compression round

There are compression rounds. Each round takes 32-bit values as input, and performs the following operations:

where must handle a carry .

The SHA-256 compression function

Define as a table mapping a -bit input to an output interleaved with zero bits. We do not require a separate table for range checks because can be used.

Modular addition

To implement addition modulo , we note that this is equivalent to adding the operands using field addition, and then masking away all but the lowest 32 bits of the result. For example, if we have two operands and :

we decompose each operand (along with the result) into 16-bit chunks:

and then reformulate the constraint using field addition:

More generally, any bit-decomposition of the output can be used, not just a decomposition into 16-bit chunks. Note that this correctly handles the carry from .

This constraint requires that each chunk is correctly range-checked (or else an assignment could overflow the field).

  • The operand and result chunks can be constrained using , by looking up each chunk in the "dense" column within a subset of the table. This way we additionally get the "spread" form of the output for free; in particular this is true for the output of the bottom-right which becomes , and the output of the leftmost which becomes . We will use this below to optimize and .

  • must be constrained to the precise range of allowed carry values for the number of operands. We do this with a small range constraint.

Maj function

can be done in lookups: chunks

  • As mentioned above, after the first round we already have in spread form . Similarly, and are equal to the and respectively of the previous round, and therefore in the steady state we already have them in spread form and . In fact we can also assume we have them in spread form in the first round, either from the fixed IV or from the use of to reduce the output of the feedforward in the previous block.
  • Add the spread forms in the field: ;
    • We can add them as -bit words or in pieces; it's equivalent
  • Witness the compressed even bits and the compressed odd bits for ;
  • Constrain , where is the function output.

Note: by "even" bits we mean the bits of weight an even-power of , i.e. of weight . Similarly by "odd" bits we mean the bits of weight an odd-power of .

Ch function

TODO: can probably be optimized to or lookups using an additional table.

can be done in lookups: chunks

  • As mentioned above, after the first round we already have in spread form . Similarly, and are equal to the and respectively of the previous round, and therefore in the steady state we already have them in spread form and . In fact we can also assume we have them in spread form in the first round, either from the fixed IV or from the use of to reduce the output of the feedforward in the previous block.
  • Calculate and , where .
    • We can add them as -bit words or in pieces; it's equivalent.
    • works to compute the spread of even though negation and do not commute in general. It works because each spread bit in is subtracted from , so there are no borrows.
  • Witness such that , and similarly for .
  • is the function output.

Σ_0 function

can be done in lookups.

To achieve this we first split into pieces , of lengths bits respectively counting from the little end. At the same time we obtain the spread forms of these pieces. This can all be done in two PLONK rows, because the and -bit pieces can be handled using lookups, and the -bit piece can be split into -bit subpieces. The latter and the remaining -bit piece can be range-checked by polynomial constraints in parallel with the two lookups, two small pieces in each row. The spread forms of these small pieces are found by interpolation.

Note that the splitting into pieces can be combined with the reduction of , i.e. no extra lookups are needed for the latter. In the last round we reduce after adding the feedforward (requiring a carry of up to which is fine).

is equivalent to :

Then, using more lookups we obtain the result as the even bits of a linear combination of the pieces:

That is, we witness the compressed even bits and the compressed odd bits , and constrain where is the function output.

Σ_1 function

can be done in lookups.

To achieve this we first split into pieces , of lengths bits respectively counting from the little end. At the same time we obtain the spread forms of these pieces. This can all be done in two PLONK rows, because the and -bit pieces can be handled using lookups, the -bit piece can be split into and -bit subpieces, and the -bit piece can be split into -bit subpieces. The four small pieces can be range-checked by polynomial constraints in parallel with the two lookups, two small pieces in each row. The spread forms of these small pieces are found by interpolation.

Note that the splitting into pieces can be combined with the reduction of , i.e. no extra lookups are needed for the latter. In the last round we reduce after adding the feedforward (requiring a carry of up to which is fine).

is equivalent to .

Then, using more lookups we obtain the result as the even bits of a linear combination of the pieces, in the same way we did for :

That is, we witness the compressed even bits and the compressed odd bits , and constrain where is the function output.

Block decomposition

For each block of the padded message, words of bits each are constructed as follows:

  • The first are obtained by splitting into -bit blocks
  • The remaining words are constructed using the formula: for .

Note: -based numbering is used for the word indices.

Note: is a right-shift, not a rotation.

σ_0 function

is equivalent to .

As above but with pieces of lengths counting from the little end. Split into two -bit subpieces.

σ_1 function

is equivalent to .

TODO: this diagram doesn't match the expression on the right. This is just for consistency with the other diagrams.

As above but with pieces of lengths counting from the little end. Split into -bit subpieces.

Message scheduling

We apply to , and to . In order to avoid redundant applications of , we can merge the splitting into pieces for and in the case of . Merging the piece lengths and gives pieces of lengths .

If we can do the merged split in rows (as opposed to a total of rows when splitting for and separately), we save rows.

These might even be doable in rows; not sure. —Daira

We can merge the reduction mod of into their splitting when they are used to compute subsequent words, similarly to what we did for and in the round function.

We will still need to reduce since they are not split. (Technically we could leave them unreduced since they will be reduced later when they are used to compute and -- but that would require handling a carry of up to rather than , so it's not worth the complexity.)

The resulting message schedule cost is:

  • rows to constrain to bits
    • This is technically optional, but let's do it for robustness, since the rest of the input is constrained for free.
  • rows to split into -bit pieces
  • rows to split into -bit pieces (merged with a reduction for )
  • rows to split into -bit pieces (merged with a reduction)
  • rows to extract the results of for
  • rows to extract the results of for
  • rows to reduce
  • rows.

Overall cost

For each round:

  • rows for
  • rows for
  • rows for
  • rows for
  • and are always free
  • per round

This gives rows for all of "step 3", to which we need to add:

  • rows for message scheduling
  • rows for reductions mod in "step 4"

giving a total of rows.

Tables

We only require one table , with rows and columns. We need a tag column to allow selecting -bit subsets of the table for and .

spread table

rowtagtable (16b)spread (32b)
0000000000000000000000000000000000000000000000000
0000000000000000100000000000000000000000000000001
0000000000000001000000000000000000000000000000100
0000000000000001100000000000000000000000000000101
...0......
0000000000111111100000000000000000001010101010101
1000000001000000000000000000000000100000000000000
...1......
1000000111111111100000000000001010101010101010101
...2......
2000001111111111100000000010101010101010101010101
...3......
3000111111111111100000001010101010101010101010101
...4......
4001111111111111100000101010101010101010101010101
...5......
5111111111111111101010101010101010101010101010101

For example, to do an -bit lookup, we polynomial-constrain the tag to be in . For the most common case of a -bit lookup, we don't need to constrain the tag. Note that we can fill any unused rows beyond with a duplicate entry, e.g. all-zeroes.

Gates

Choice gate

Input from previous operations:

  • 64-bit spread forms of 32-bit words , assumed to be constrained by previous operations
    • in practice, we'll have the spread forms of after they've been decomposed into 16-bit subpieces
  • is defined as

E ∧ F

s_ch
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

¬E ∧ G

s_ch_neg
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_ch (choice):
  • s_ch_neg (negation): s_ch with an extra negation check
  • lookup on
  • permutation between

Output:

Majority gate

Input from previous operations:

  • 64-bit spread forms of 32-bit words , assumed to be constrained by previous operations
    • in practice, we'll have the spread forms of after they've been decomposed into -bit subpieces
s_maj
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_maj (majority):
  • lookup on
  • permutation between

Output:

Σ_0 gate

is a 32-bit word split into -bit chunks, starting from the little end. We refer to these chunks as respectively, and further split into three 3-bit chunks . We witness the spread versions of the small chunks.

s_upp_sigma_0
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_upp_sigma_0 ( constraint):

  • lookup on
  • 2-bit range check and 2-bit spread check on
  • 3-bit range check and 3-bit spread check on

(see section Helper gates)

Output:

Σ_1 gate

is a 32-bit word split into -bit chunks, starting from the little end. We refer to these chunks as respectively, and further split into two 3-bit chunks and into (2,3)-bit chunks . We witness the spread versions of the small chunks.

s_upp_sigma_1
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_upp_sigma_1 ( constraint):

  • lookup on
  • 2-bit range check and 2-bit spread check on
  • 3-bit range check and 3-bit spread check on

(see section Helper gates)

Output:

σ_0 gate

v1

v1 of the gate takes in a word that's split into -bit chunks (already constrained by message scheduling). We refer to these chunks respectively as is further split into two 2-bit chunks We witness the spread versions of the small chunks. We already have and from the message scheduling.

is equivalent to .

s_low_sigma_0
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_low_sigma_0 ( v1 constraint):

  • check that b was properly split into subsections for 4-bit pieces.
  • 2-bit range check and 2-bit spread check on
  • 3-bit range check and 3-bit spread check on

v2

v2 of the gate takes in a word that's split into -bit chunks (already constrained by message scheduling). We refer to these chunks respectively as We already have from the message scheduling. The 1-bit remain unchanged by the spread operation and can be used directly. We further split into two 2-bit chunks We witness the spread versions of the small chunks.

is equivalent to .

s_low_sigma_0_v2
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_low_sigma_0_v2 ( v2 constraint):

  • check that b was properly split into subsections for 4-bit pieces.
  • 2-bit range check and 2-bit spread check on
  • 3-bit range check and 3-bit spread check on

σ_1 gate

v1

v1 of the gate takes in a word that's split into -bit chunks (already constrained by message scheduling). We refer to these chunks respectively as is further split into -bit chunks We witness the spread versions of the small chunks. We already have and from the message scheduling.

is equivalent to .

s_low_sigma_1
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_low_sigma_1 ( v1 constraint):

  • check that b was properly split into subsections for 7-bit pieces.

  • 2-bit range check and 2-bit spread check on

  • 3-bit range check and 3-bit spread check on

v2

v2 of the gate takes in a word that's split into -bit chunks (already constrained by message scheduling). We refer to these chunks respectively as We already have from the message scheduling. The 1-bit remain unchanged by the spread operation and can be used directly. We further split into two 2-bit chunks We witness the spread versions of the small chunks.

is equivalent to .

s_low_sigma_1_v2
0{0,1,2,3,4,5}
1{0,1,2,3,4,5}
0{0,1,2,3,4,5}
0{0,1,2,3,4,5}

Constraints:

  • s_low_sigma_1_v2 ( v2 constraint):

  • check that b was properly split into subsections for 4-bit pieces.
  • 2-bit range check and 2-bit spread check on
  • 3-bit range check and 3-bit spread check on

Helper gates

Small range constraints

Let . Constraining this expression to equal zero enforces that is in

2-bit range check

sr2
1a

2-bit spread

ss2
1aa'

with interpolation polynomials:

  • ()
  • ()
  • ()
  • ()

3-bit range check

sr3
1a

3-bit spread

ss3
1aa'

with interpolation polynomials:

  • ()
  • ()
  • ()
  • ()
  • ()
  • ()
  • ()
  • ()

reduce_6 gate

Addition of 6 elements

Input:

Check:

Assume inputs are constrained to 16 bits.

  • Addition gate (sa):
  • Carry gate (sc):
sasc
10
11

Assume inputs are constrained to 16 bits.

  • Addition gate (sa):
  • Carry gate (sc):
sasc
00
11
00
10

reduce_7 gate

Addition of 7 elements

Input:

Check:

Assume inputs are constrained to 16 bits.

  • Addition gate (sa):
  • Carry gate (sc):
sasc
10
11

Message scheduling region

For each block of the padded message, words of bits each are constructed as follows:

  • the first are obtained by splitting into -bit blocks
  • the remaining words are constructed using the formula: for .
swsd0sd1sd2sd3ss0ss0_v2ss1ss1_v2
010000000{0,1,2,3,4,5}
100000000{0,1,2,3,4,5}
011000000{0,1,2,3,4}
100000000{0,1,2}
000000000{0,1,2,3,4,5}
000001000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
.....................................................
000000000{0,1,2,3}
0101000000
1000000000
000000000{0,1,2,3,4,5}
000000100{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
000000001{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
.....................................................
010010000{0,1,2,3}
000000000{0,1}
000000000{0,1,2,3,4,5}
000000001{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
.....................................................
010000000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}
010000000{0,1,2,3,4,5}
000000000{0,1,2,3,4,5}

Constraints:

  • sw: construct word using
  • sd0: decomposition gate for
  • sd1: decomposition gate for (split into -bit pieces)
  • sd2: decomposition gate for (split into -bit pieces)
  • sd3: decomposition gate for (split into -bit pieces)

Compression region

+----------------------------------------------------------+
|                                                          |
|          decompose E,                                    |
|          Σ_1(E)                                          |
|                                                          |
|                  +---------------------------------------+
|                  |                                       |
|                  |        reduce_5() to get H'           |
|                  |                                       |
+----------------------------------------------------------+
|          decompose F, decompose G                        |
|                                                          |
|                        Ch(E,F,G)                         |
|                                                          |
+----------------------------------------------------------+
|                                                          |
|          decompose A,                                    |
|          Σ_0(A)                                          |
|                                                          |
|                                                          |
|                  +---------------------------------------+
|                  |                                       |
|                  |        reduce_7() to get A_new,       |
|                  |              using H'                 |
|                  |                                       |
+------------------+---------------------------------------+
|          decompose B, decompose C                        |
|                                                          |
|          Maj(A,B,C)                                      |
|                                                          |
|                  +---------------------------------------+
|                  |        reduce_6() to get E_new,       |
|                  |              using H'                 |
+------------------+---------------------------------------+

Initial round:

s_digestsd_abcdsd_efghss0ss1s_majs_ch_negs_chs_a_news_e_news_h_prime
00100000000{0,1,2}
00000000000{0,1}
00000000000{0,1,2,3,4,5}
00001000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00100000000{0,1,2}
00000000000{0,1}
00100000000{0,1,2}
00000000000{0,1}
00000000000{0,1,2,3,4,5}
00000001001{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000010{0,1,2,3,4,5}
00000010000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
01000000000{0,1,2}
00000000000{0,1}
00000000000{0,1,2,3,4,5}
00010000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
01000000000{0,1,2}
00000000000{0,1}
01000000000{0,1,2}
00000000000{0,1}
00000000000{0,1,2,3,4,5}
00000100100{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}

Steady-state:

s_digestsd_abcdsd_efghss0ss1s_majs_ch_negs_chs_a_news_e_news_h_prime
00100000000{0,1,2}
00000000000{0,1}
00000000000{0,1,2,3,4,5}
00001000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000001001{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000010{0,1,2,3,4,5}
00000010000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
01000000000{0,1,2}
00000000000{0,1}
00000000000{0,1,2,3,4,5}
00010000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000100100{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}
00000000000{0,1,2,3,4,5}

Final digest:

s_digestsd_abcdsd_efghss0ss1s_majs_ch_negs_chs_a_news_e_news_h_prime
10000000000000
00000000000000
10000000000000
00000000000000

Background Material

This section covers the background material required to understand the Halo 2 proving system. It is targeted at an ELI15 (Explain It Like I'm 15) level; if you think anything could do with additional explanation, let us know!

该部分包含了理解Halo 2证明系统所必须的背景资料。该部分面向的是ELI15水平(即读者只需15岁知识水平);如果您想进一步提供补充材料,联系我们!

Fields

A fundamental component of many cryptographic protocols is the algebraic structure known as a field. Fields are sets of objects (usually numbers) with two associated binary operators and such that various field axioms hold. The real numbers are an example of a field with uncountably many elements.

对于众多密码学协议来说, —— 一种代数结构,都是一个最基本的组件。域,就是指拥有 两个二元运算的集合(通常是数集),并且满足一系列 域公理。举例来说,实数集 就是一个拥有不可数无穷多元素的域。

Halo makes use of finite fields which have a finite number of elements. Finite fields are fully classified as follows:

Halo运用有限域,所谓有限域是指域的元素个数是有限的。有限域完全分类如下:

  • if is a finite field, it contains elements for some integer and some prime ;

  • 如果 是有限域,那么它包含 个元素,其中 是整数且 是一个素数。

  • any two finite fields with the same number of elements are isomorphic. In particular, all of the arithmetic in a prime field is isomorphic to addition and multiplication of integers modulo , i.e. in . This is why we often refer to as the modulus.

  • 任意两个有相同元素个数的有限域是同构的。特别的,素域 上的算数运算与整数 modulo 上的加法和乘法是同构的,一个例子是,。这就是我们将 作为 modulus 的原因。

We'll write a field as where . The prime is called its characteristic. In the cases where the field is a -degree extension of the field . (By analogy, the complex numbers are an extension of the real numbers.) However, in Halo we do not use extension fields. Whenever we write we are referring to what we call a prime field which has a prime number of elements, i.e. .

我们定义一个域 其中 . 素数 称为它的 特征。 如果 , 那么域 就是域 阶扩张。 (相类似,复数 就是实数域的扩张)。但是, 在Halo中,我们并不使用扩域。当我们写 我们指的是拥有素数 个元素的 素域,也就是说此时

Important notes:

重要注释:

  • There are two special elements in any field: , the additive identity, and , the multiplicative identity.

  • 任何域中,都有两个特殊的元素: ,加法的单位元; ,乘法的单位元。

  • The least significant bit of a field element, when represented as an integer in binary format, can be interpreted as its "sign" to help distinguish it from its additive inverse (negation). This is because for some nonzero element which has a least significant bit we have that has a least significant bit , and vice versa. We could also use whether or not an element is larger than to give it a "sign."

  • 一个域中的元素,其在二进制表示中的最低位,可以用来代表它在域上的“符号”以区分它的加法逆元(即负数)。这是因为,对任意一个最低位为 的非零元素 其加法逆元 的最低位一定是 ,反之亦然。我们也可以用一个元素是不是大于 来作为其“符号”。

Finite fields will be useful later for constructing polynomials and elliptic curves. Elliptic curves are examples of groups, which we discuss next.

有限域对于后文中构建 多项式椭圆曲线 是很有用处的。 椭圆曲线是一个群,我们将马上对群展开讨论。

Groups

Groups are simpler and more limited than fields; they have only one binary operator and fewer axioms. They also have an identity, which we'll denote as .

与域相比,群更加简单,并且更有限(???);群只有一个二元运算 ,和更少的公理。群也有一个单位元,我们用 表示。

Any non-zero element in a group has an inverse , which is the unique element such that .

群中任意一个非零元素 必有一个 唯一逆元,满足

For example, the set of nonzero elements of forms a group, where the group operation is given by multiplication on the field.

举个例子,域 中所有非零元素形成一个群,同时定义该群的运算就是域上的乘法。

(aside) Additive vs multiplicative notation

(备注) 加法 vs 乘法符号

If is written as or omitted (i.e. written as ), the identity as , and inversion as , as we did above, then we say that the group is "written multiplicatively". If is written as , the identity as or , and inversion as , then we say it is "written additively".

如果将 写做 或是干脆不写 (比如: 将 写做 ), 那么正如上文所述,单位元 就写做 , 它的逆元就是 ,我们说这样的群“被写作乘”。而如果将 视为 , 那么它的单位元就是 或者 , 它的逆元就是 , 我们说这样的群“被写做加”。

It's conventional to use additive notation for elliptic curve groups, and multiplicative notation when the elements come from a finite field.

通常,椭圆曲线用加法符号, 而对于有限域中的元素用乘法符号

When additive notation is used, we also write

当我们使用加法符号时,将写如下式子:

for nonnegative and call this "scalar multiplication"; we also often use uppercase letters for variables denoting group elements. When multiplicative notation is used, we also write

对于任意非负 我们称上式为“标量乘法”;通常,我们使用大写字母变量来表示群的元素。当我们使用乘法符号时,如下等式

and call this "exponentiation". In either case we call the scalar such that or the "discrete logarithm" of to base . We can extend scalars to negative integers by inversion, i.e. or .

就被称为“指数”。无论上述那种情况,我们都将满足 称为 在基 下的“离散对数”。 我们可以通过求逆运算来 扩展标量,比如: 或者 .

The order of an element of a finite group is defined as the smallest positive integer such that (in multiplicative notation) or (in additive notation). The order of the group is the number of elements.

有限域元素 定义为满足如下条件的最小的正整数 (乘法符号)或者 (加法表示)。 群的阶 就是指群包含的元素的个数。

Groups always have a generating set, which is a set of elements such that we can produce any element of the group as (in multiplicative terminology) a product of powers of those elements. So if the generating set is , we can produce any element of the group as . There can be many different generating sets for a given group.

群总有一个 生成集,所谓生成集是这样一个集合,可以使用该集合中的元素通过这些元素的乘方运算(乘法术语)来生成群中的任意一个元素。 如果,生成集是 , 我们就可以通过 生成群的所有元素。对于一个给定的群,它有很多不同的生成集。

A group is called cyclic if it has a (not necessarily unique) generating set with only a single element — call it . In that case we can say that generates the group, and that the order of is the order of the group.

如果一个群的存在一个生成集(不一定是唯一的)只有一个元素,记为 ,那么这个群就是一个循环群。进而,我们成 生成了这个群,并且 的阶就是该群的阶。

Any finite cyclic group of order is isomorphic to the integers modulo (denoted ), such that:

任意一个阶为 的有限循环群 与整数modulo (记为 )是同构的,满足:

  • the operation in corresponds to addition modulo ;

  • the identity in corresponds to ;

  • some generator corresponds to .

  • 上的运算 与modulo 的加法对应;

  • 的单位元是 ;

  • 有一个生成元 .

Given a generator , the isomorphism is always easy to compute in the direction; it is just (or in additive notation, ). It may be difficult in general to compute in the direction; we'll discuss this further when we come to elliptic curves.

对于一个给定的生成元 ,容易证明 是成立的,因为(或是用加法符号, )。通常,证明 会难一些。我们将在椭圆曲线中进一步讨论这个问题。

If the order of a finite group is prime, then the group is cyclic, and every non-identity element is a generator.

如果一个有限群的阶 是一个素数,那么该群是个循环群,并且每个非单位元元素都是其生成元

The multiplicative group of a finite field

有限域的乘法子群

We use the notation for the multiplicative group (i.e. the group operation is multiplication in ) over the set .

我们用符号 来代表集合 上的乘法群(比如,群的运算就是 的乘法)。

A quick way of obtaining the inverse in is . The reason for this stems from Fermat's little theorem, which states that for any integer . If is nonzero, we can divide by twice to get

一个快速求逆的方法是 is 。这是因为,由费马小定理,可知如果 是一个素数, 对任意整数 不是 的倍数,都有 。如果 是非零整数,那么我们可以除两次 就获得

Let's assume that is a generator of , so it has order (equal to the number of elements in ). Therefore, for any element in there is a unique integer such that .

的生成元,所以 的阶是 (等于 的元素的个数). 因此,对任意一个 都存在唯一一个 满足 .

Notice that where can really be interpreted as where and . Indeed, it holds that for all . As a result the multiplication of nonzero field elements can be interpreted as addition modulo with respect to some fixed generator . The addition just happens "in the exponent."

值得注意的是 其中 确实可以表示成 其中 并且 。实际上,对任意 它也保持了如下运算 。因此,域上非零元素的乘法就可以表示成关于某个特定生成元 的在 modulo 上的加法。这个加法,就出现在“指数”上

This is another way to look at where comes from for computing inverses in the field:

这是另一种理解 就是域元素的逆元的方法:

so .

Montgomery's Trick

蒙哥马利花招

Montgomery's trick, named after Peter Montgomery (RIP) is a way to compute many group inversions at the same time. It is commonly used to compute inversions in , which are quite computationally expensive compared to multiplication.

蒙哥马利花招,以彼得 · 蒙哥马利 (RIP) 得名,是同时计算很多群元素的逆元的一种方法。 它通常用于在 中求逆,求逆运算 要比乘法运算代价大得多。

Imagine we need to compute the inverses of three nonzero elements . Instead, we'll compute the products and , and compute the inversion

假设我们要计算三个非零元素 的逆元。不似常规,我们将计算如下两个积 ,并且计算如下的逆

We can now multiply by to obtain and multiply by to obtain , which we can then multiply by to obtain their respective inverses.

现在我们可以 乘以 以获得 ,并且 乘以 得到 , 进一步该值分别乘以 就分别获得了想要的逆元。

This technique generalizes to arbitrary numbers of group elements with just a single inversion necessary.

该技术可以推广,仅仅一次求逆运算就可以计算出任意个数群元素的逆。

Multiplicative subgroups

乘法子群

A subgroup of a group with operation , is a subset of elements of that also form a group under .

所谓群 下的 子群 就是, 中元素的一个子集在 下仍然是一个群。

In the previous section we said that is a generator of the -order multiplicative group . This group has composite order, and so by the Chinese remainder theorem1 it has strict subgroups. As an example let's imagine that , and so factors into . Thus, there is a generator of the -order subgroup and a generator of the -order subgroup. All elements in , therefore, can be written uniquely as for some (modulo ) and some (modulo ).

在前面的章节中,我们说 -阶群 的生成元。 该群拥有 合数 阶,所以依据中国剩余定理1 它有真子群。举个例子,假设 ,那么 可以分解为 。因此,存在一个 以 为生成元的 -阶子群和一个以 为生成元的 -阶子群。进一步, 中所有元素都可以表示为 其中 (modulo ) and some (modulo ).

If we have notice what happens when we compute

如果我们有 请注意如下计算过程

we have effectively "killed" the -order subgroup component, producing a value in the -order subgroup.

我们“消灭”了 -阶子群部分,仅仅只用 -阶子群就生成了这个值。

Lagrange's theorem (group theory) states that the order of any subgroup of a finite group divides the order of . Therefore, the order of any subgroup of must divide

拉格朗日定理 (群论) 告诉我们,有限群 的任意一个子群 的阶能整除 的阶。因此 的任何子群的阶必定能整除

PLONK-based proving systems like Halo 2 are more convenient to use with fields that have a large number of multiplicative subgroups with a "smooth" distribution (which makes the performance cliffs smaller and more granular as circuit sizes increase). The Pallas and Vesta curves specifically have primes of the form

PLONK-based 证明系统, 如 Halo 2,可以更方便的利用拥有大量乘法子群的域,并且这些子群是“平滑”分布的(????)(好处是使得性能悬崖更下,并且可以以更细的力度增长电路规模)。Pallas 和 Vesta 曲线有如下形式的素数

with and odd (i.e. has 32 lower zero-bits). This means they have multiplicative subgroups of order for all . These 2-adic subgroups are nice for efficient FFTs, as well as enabling a wide variety of circuit sizes.

其中 并且 奇数 (这就是说, 的低32位都是 )。这意味着,它们有阶为 的乘法子群,其中 。这些 2-adic 乘法子群对efficient FFTs 十分友好,而且也可以支持多种电路规模。

Square roots

平方根

In a field exactly half of all nonzero elements are squares; the remainder are non-squares or "quadratic non-residues". In order to see why, consider an that generates the -order multiplicative subgroup of (this exists because is divisible by since is a prime greater than ) and that generates the -order multiplicative subgroup of where . Then every element can be written uniquely as with and . Half of all elements will have and the other half will have .

在域 有一半的非零元素都是完全平方元素;剩下的就是非平方或者“二次非剩余”。为了说明此一事实,考虑 生成的 的 2-阶乘法子群(该子群必然存在,因为当 是一个大于等于 的素数的时候, 能被 整除)和一个由 生成的 -阶乘法子群,其中 。进而每个元素 均可以唯一地表示为 其中 and 。那么有一半的元素满足 而另一半元素满足 .

Let's consider the simple case where and so is odd (if is even, then would be divisible by , which contradicts being ). If is a square, then there must exist such that . But this means that

考虑一个简单的例子, 那么 必是一个奇数 (如果 是偶数,则 必能被 整除,而这与 being 矛盾)。 如果 是一个完全平方数,则必存在一个 使得 。这就意味着,

In other words, all squares in this particular field do not generate the -order multiplicative subgroup, and so since half of the elements generate the -order subgroup then at most half of the elements are square. In fact exactly half of the elements are square (since squaring each nonsquare element gives a unique square). This means we can assume all squares can be written as for some , and therefore finding the square root is a matter of exponentiating by .

换句话说,某个特定域中的完全平方数不可能生成其 -阶乘法子群,而且由于有一半的元素可以产生其 -阶子群,所以该域中至多有一般的元素是完全平方数。事实上,有且仅有一半的元素是完全平方数(这是因为,每一个非平方元素的平方都是唯一的)。这就意味着,我们可以假设所有的完全平方数都可以表示为 对某个 ,因此求平方根就变成了一个指数运算,指数就是

In the event that then things get more complicated because does not exist. Let's write as with odd. The case is impossible, and the case is what we already described, so consider . generates a -order multiplicative subgroup and generates the odd -order multiplicative subgroup. Then every element can be written as for and . If the element is a square, then there exists some which can be written for and . This means that , therefore we have , and . would have to be even in this case because otherwise it would be impossible to have for any . In the case that is not a square, then is odd, and so half of all elements are squares.

而如果 那问题就变得复杂得多,因为 并不存在。 记 = 其中 是奇数。(??不妨设p=4n + 1 => p - 1 = 4n从而k必然是>=2。并且,k=1上文也没讨论啊)明显 生成一个 -阶乘法子群而 生成一个奇数 -阶得乘法子群。 进而每个元素 都可以表示为 其中 并且 。如果某元素是完全平方数,就是说存在 本身可以表示为 对于 。这意味着 , 因此我们推出 ,并且 。那么在这种情况下 就必须是一个偶数,否则对任意 , 就不能成立。反之,如果 不是一个完全平方数,那么 就是一个奇数。综上,一半得元素是完全平方数。

In order to compute the square root, we can first raise the element to the power to "kill" the -order component, giving

为了计算平方根,我们首先将 升次到 以“消灭” -阶部分,计算

and then raise this result to the power to undo the effect of the original exponentiation on the -order component:

然后在此基础上计算 次方,以消除其 -阶部分原始指数的影响:

(since is relatively prime to ). This leaves bare the value which we can trivially handle. We can similarly kill the -order component to obtain , and put the values together to obtain the square root.

(因为 是互素的)。这就暴露出 的值可以让我们进一步处理。 相似的,我们可以消除 -阶部分以获得 ,将这两个值合起来就得出了平方根。

It turns out that in the cases there are simpler algorithms that merge several of these exponentiations together for efficiency. For other values of , the only known way is to manually extract by squaring until you obtain the identity for every single bit of . This is the essence of the Tonelli-Shanks square root algorithm and describes the general strategy. (There is another square root algorithm that uses quadratic extension fields, but it doesn't pay off in efficiency until the prime becomes quite large.)

已经证明当 时,有更简便的方法来合并这些指数以提高效率。 而对于其他的 值,唯一获取 的方法就是,不断平方以最终确定 的每一位。 这就是 Tonelli-Shanks square root algorithm 算法的本质,并且该算法还描述了一半的策略。 (当然还有另外一种用二次扩域的求取平方根的算法,但是知道素数变得相当大时,该算法才有效率优势)。

Roots of unity

单位根

In the previous sections we wrote with odd, and stated that an element generated the -order subgroup. For convenience, let's denote The elements are known as the th roots of unity.

在前一章节,我们令 其中 是奇数,并且阐明 元素 生成其 -阶子群。 位方便起见,不妨设 。那么元素 都被称为 单位根

The primitive root of unity, is an th root of unity such that except when .

所谓 主单位根,是满足如下条件的 次单位根 除非 .

Important notes:

重要补充:

  • If is an th root of unity, satisfies If then

  • 如果 是一个 次单位根,那么 满足 。如果 ,那么

  • Equivalently, the roots of unity are solutions to the equation

  • 相应地,单位根集合就是如下方程的解

  • ("Negation lemma"). Proof: Since the order of is , Therefore,

  • ("负数引理")。证明: 因为 的阶是 , 。因此,

  • ("Halving lemma"). Proof: In other words, if we square each element in the th roots of unity, we would get back only half the elements, (i.e. the th roots of unity). There is a two-to-one mapping between the elements and their squares.

  • ("折半引理")。证明:
    换句话说,如果我们平方每一个 次单位根集合中的元素,我们只会得到一半的元素 (这就是 次单位根)。 在元素和它们的平方之间存在一个 的映射。

    References

    参考

Polynomials

Let be a polynomial over with formal indeterminate . As an example,

defines a degree- polynomial. is referred to as the constant term. Polynomials of degree have coefficients. We will often want to compute the result of replacing the formal indeterminate with some concrete value , which we denote by .

In mathematics this is commonly referred to as "evaluating at a point ". The word "point" here stems from the geometrical usage of polynomials in the form , where is the coordinate of a point in two-dimensional space. However, the polynomials we deal with are almost always constrained to equal zero, and will be an element of some field. This should not be confused with points on an elliptic curve, which we also make use of, but never in the context of polynomial evaluation.

Important notes:

  • Multiplication of polynomials produces a product polynomial that is the sum of the degrees of its factors. Polynomial division subtracts from the degree.
  • Given a polynomial of degree , if we obtain evaluations of the polynomial at distinct points then these evaluations perfectly define the polynomial. In other words, given these evaluations we can obtain a unique polynomial of degree via polynomial interpolation.
  • is the coefficient representation of the polynomial . Equivalently, we could use its evaluation representation at distinct points. Either representation uniquely specifies the same polynomial.

(aside) Horner's rule

Horner's rule allows for efficient evaluation of a polynomial of degree , using only multiplications and additions. It is the following identity:

Fast Fourier Transform (FFT)

The FFT is an efficient way of converting between the coefficient and evaluation representations of a polynomial. It evaluates the polynomial at the th roots of unity where is a primitive th root of unity. By exploiting symmetries in the roots of unity, each round of the FFT reduces the evaluation into a problem only half the size. Most commonly we use polynomials of length some power of two, , and apply the halving reduction recursively.

Motivation: Fast polynomial multiplication

In the coefficient representation, it takes operations to multiply two polynomials :

where each of the terms in the first polynomial has to be multiplied by the terms of the second polynomial.

In the evaluation representation, however, polynomial multiplication only requires operations:

where each evaluation is multiplied pointwise.

This suggests the following strategy for fast polynomial multiplication:

  1. Evaluate polynomials at all points;
  2. Perform fast pointwise multiplication in the evaluation representation ();
  3. Convert back to the coefficient representation.

The challenge now is how to evaluate and interpolate the polynomials efficiently. Naively, evaluating a polynomial at points would require operations (we use the Horner's rule at each point):

For convenience, we will denote the matrices above as:

( is known as the Discrete Fourier Transform of ; is also called the Vandermonde matrix.)

The (radix-2) Cooley-Tukey algorithm

Our strategy is to divide a DFT of size into two interleaved DFTs of size . Given the polynomial we split it up into even and odd terms:

To recover the original polynomial, we do

Trying this out on points and , we start to notice some symmetries:

Notice that we are only evaluating and over half the domain (halving lemma). This gives us all the terms we need to reconstruct over the full domain : which means we have transformed a length- DFT into two length- DFTs.

We choose to be a power of two (by zero-padding if needed), and apply this divide-and-conquer strategy recursively. By the Master Theorem1, this gives us an evaluation algorithm with operations, also known as the Fast Fourier Transform (FFT).

Inverse FFT

So we've evaluated our polynomials and multiplied them pointwise. What remains is to convert the product from the evaluation representation back to coefficient representation. To do this, we simply call the FFT on the evaluation representation. However, this time we also:

  • replace by in the Vandermonde matrix, and
  • multiply our final result by a factor of .

In other words:

(To understand why the inverse FFT has a similar form to the FFT, refer to Slide 13-1 of 2. The below image was also taken from 2.)

The Schwartz-Zippel lemma

The Schwartz-Zippel lemma informally states that "different polynomials are different at most points." Formally, it can be written as follows:

Let be a nonzero polynomial of variables with degree . Let be a finite set of numbers with at least elements in it. If we choose random from ,

In the familiar univariate case , this reduces to saying that a nonzero polynomial of degree has at most roots.

The Schwartz-Zippel lemma is used in polynomial equality testing. Given two multi-variate polynomials and of degrees respectively, we can test if for random where the size of is at least If the two polynomials are identical, this will always be true, whereas if the two polynomials are different then the equality holds with probability at most .

Vanishing polynomial

Consider the order- multiplicative subgroup with primitive root of unity . For all we have In other words, every element of fulfils the equation

meaning every element is a root of We call the vanishing polynomial over because it evaluates to zero on all elements of

This comes in particularly handy when checking polynomial constraints. For instance, to check that over we simply have to check that is some multiple of . In other words, if dividing our constraint by the vanishing polynomial still yields some polynomial we are satisfied that over

Lagrange basis functions

TODO: explain what a basis is in general (briefly).

Polynomials are commonly written in the monomial basis (e.g. ). However, when working over a multiplicative subgroup of order , we find a more natural expression in the Lagrange basis.

Consider the order- multiplicative subgroup with primitive root of unity . The Lagrange basis corresponding to this subgroup is a set of functions , where

We can write this more compactly as where is the Kronecker delta function.

Now, we can write our polynomial as a linear combination of Lagrange basis functions,

which is equivalent to saying that evaluates to at , to at , to at and so on.

When working over a multiplicative subgroup, the Lagrange basis function has a convenient sparse representation of the form

where is the barycentric weight. (To understand how this form was derived, refer to 3.) For we have .

Suppose we are given a set of evaluation points . Since we cannot assume that the 's form a multiplicative subgroup, we consider also the Lagrange polynomials 's in the general case. Then we can construct:

Here, every will produce a zero numerator term causing the whole product to evaluate to zero. On the other hand, will evaluate to at every term, resulting in an overall product of one. This gives the desired Kronecker delta behaviour on the set .

Lagrange interpolation

Given a polynomial in its evaluation representation

we can reconstruct its coefficient form in the Lagrange basis:

where

References

Cryptographic groups

密码学的群

In the section Inverses and groups we introduced the concept of groups. A group has an identity and a group operation. In this section we will write groups additively, i.e. the identity is and the group operation is .

在章节 中,我们引入了 的概念。 群有一个单位元和一个群运算。本节,我们将写一个加法群,也就是说,它的单位元是 ,群运算是

Some groups can be used as cryptographic groups. At the risk of oversimplifying, this means that the problem of finding a discrete logarithm of a group element to a given base , i.e. finding such that , is hard in general.

有些群可以被用于密码学,是为 密码学的群。这意味着,通常来讲,找到一个在基 下群元素 的离散对数 是困难的。找到离散对数,就是找到一个 使它满足

Pedersen commitment

Pedersen承诺

The Pedersen commitment [P99] is a way to commit to a secret message in a verifiable way. It uses two random public generators where is a cryptographic group of order . A random secret is chosen in , and the message to commit to is from any subset of . The commitment is

Pedersen承诺 [P99] 是一种以可验证的方式对一个秘密消息进行承诺的方法。 它使用两个公开的、随机的生成元 是一个 阶的密码群。 A random secret is chosen in 在 上随机选取一个秘密 ,而欲承诺的消息 来自于 的任意一个子集。那么该消息的承诺就是:

To open the commitment, the committer reveals and thus allowing anyone to verify that is indeed a commitment to

为了打开这个承诺,承诺者必须曝露 and ,以使任何人都能验证 确实使 的承诺。

Notice that the Pedersen commitment scheme is homomorphic:

注意,Pedersen承诺机制使同态的:

Assuming the discrete log assumption holds, Pedersen commitments are also perfectly hiding and computationally binding:

假设离散对数假设能够保持,那Pedersen承诺就是完美的隐藏(hiding),计算意义上的连结(binding)

  • hiding: the adversary chooses messages The committer commits to one of these messages Given the probability of the adversary guessing the correct is no more than .

  • 隐藏: the adversary chooses messages The committer commits to one of these messages Given the probability of the adversary guessing the correct is no more than .

  • binding: the adversary cannot pick two different messages and randomness such that

Vector Pedersen commitment

We can use a variant of the Pedersen commitment scheme to commit to multiple messages at once, . This time, we'll have to sample a corresponding number of random public generators along with a single random generator as before (for use in hiding). Then, our commitment scheme is:

TODO: is this positionally binding?

Diffie--Hellman

An example of a protocol that uses cryptographic groups is Diffie--Hellman key agreement [DH1976]. The Diffie--Hellman protocol is a method for two users, Alice and Bob, to generate a shared private key. It proceeds as follows:

  1. Alice and Bob publicly agree on two prime numbers, and where is large and is a primitive root (Note that is a generator of the group )
  2. Alice chooses a large random number as her private key. She computes her public key and sends to Bob.
  3. Similarly, Bob chooses a large random number as his private key. He computes his public key and sends to Alice.
  4. Now both Alice and Bob compute their shared key which Alice computes as and Bob computes as

A potential eavesdropper would need to derive knowing only and : in other words, they would need to either get the discrete logarithm from or from which we assume to be computationally infeasible in

More generally, protocols that use similar ideas to Diffie--Hellman are used throughout cryptography. One way of instantiating a cryptographic group is as an elliptic curve. Before we go into detail on elliptic curves, we'll describe some algorithms that can be used for any group.

Multiscalar multiplication

TODO: Pippenger's algorithm

Reference: https://jbootle.github.io/Misc/pippenger.pdf

Elliptic curves

Elliptic curves constructed over finite fields are another important cryptographic tool.

We use elliptic curves because they provide a cryptographic group, i.e. a group in which the discrete logarithm problem (discussed below) is hard.

There are several ways to define the curve equation, but for our purposes, let be a large (255-bit) field, and then let the set of solutions to for some constant define the -rational points on an elliptic curve . These coordinates are called "affine coordinates". Each of the -rational points, together with a "point at infinity" that serves as the group identity, can be interpreted as an element of a group. By convention, elliptic curve groups are written additively.

"Three points on a line sum to zero, which is the point at infinity."

The group addition law is simple: to add two points together, find the line that intersects both points and obtain the third point, and then negate its -coordinate. The case that a point is being added to itself, called point doubling, requires special handling: we find the line tangent to the point, and then find the single other point that intersects this line and then negate. Otherwise, in the event that a point is being "added" to its negation, the result is the point at infinity.

The ability to add and double points naturally gives us a way to scale them by integers, called scalars. The number of points on the curve is the group order. If this number is a prime , then the scalars can be considered as elements of a scalar field, .

Elliptic curves, when properly designed, have an important security property. Given two random elements finding such that , otherwise known as the discrete log of with respect to , is considered computationally infeasible with classical computers. This is called the elliptic curve discrete log assumption.

If an elliptic curve group has prime order (like the ones used in Halo 2), then it is a finite cyclic group. Recall from the section on groups that this implies it is isomorphic to , or equivalently, to the scalar field . Each possible generator fixes the isomorphism; then an element on the scalar side is precisely the discrete log of the corresponding group element with respect to . In the case of a cryptographically secure elliptic curve, the isomorphism is hard to compute in the direction because the elliptic curve discrete log problem is hard.

It is sometimes helpful to make use of this isomorphism by thinking of group-based cryptographic protocols and algorithms in terms of the scalars instead of in terms of the group elements. This can make proofs and notation simpler.

For instance, it has become common in papers on proof systems to use the notation to denote a group element with discrete log , where the generator is implicit.

We also used this idea in the "distinct-x theorem", in order to prove correctness of optimizations for elliptic curve scalar multiplication in Sapling, and an endomorphism-based optimization in Appendix C of the original Halo paper.

Curve arithmetic

Point doubling

The simplest situation is doubling a point . Continuing with our example , this is done first by computing the derivative

To obtain expressions for we consider

To get the expression for we substitute into the elliptic curve equation:

Comparing coefficients for the term gives us

Projective coordinates

This unfortunately requires an expensive inversion of . We can avoid this by arranging our equations to "defer" the computation of the inverse, since we often do not need the actual affine coordinate of the resulting point immediately after an individual curve operation. Let's introduce a third coordinate and scale our curve equation by like so:

Our original curve is just this curve at the restriction . If we allow the affine point to be represented by , and then we have the homogenous projective curve

Obtaining from is as simple as computing when . (When we are dealing with the point at infinity .) In this form, we now have a convenient way to defer the inversion required by doubling a point. The general strategy is to express as rational functions using and , rearrange to make their denominators the same, and then take the resulting point to have be the shared denominator and .

Projective coordinates are often, but not always, more efficient than affine coordinates. There may be exceptions to this when either we have a different way to apply Montgomery's trick, or when we're in the circuit setting where multiplications and inversions are about equally as expensive (at least in terms of circuit size).

The following shows an example of doubling a point without an inversion. Substituting with gives us

and gives us

Notice how the denominators of and are the same. Thus, instead of computing we can compute with and set to the corresponding numerators such that and . This completely avoids the need to perform an inversion when doubling, and something analogous to this can be done when adding two distinct points.

Point addition

We now add two points with distinct -coordinates, and where to obtain The line has slope

Using the expression for , we compute -coordinate of as:

Plugging the expression for into the curve equation yields

Comparing coefficients for the term gives us .


Important notes:

  • There exist efficient formulae1 for point addition that do not have edge cases (so-called "complete" formulae) and that unify the addition and doubling cases together. The result of adding a point to its negation using those formulae produces , which represents the point at infinity.
  • In addition, there are other models like the Jacobian representation where where the curve is rescaled by instead of , and this representation has even more efficient arithmetic but no unified/complete formulae.
  • We can easily compare two curve points and for equality in the homogenous projective coordinate space by "homogenizing" their Z-coordinates; the checks become and .

Curve endomorphisms

Imagine that has a primitive cube root of unity, or in other words that and so an element generates a -order multiplicative subgroup. Notice that a point on our example elliptic curve has two cousin points: , because the computation effectively kills the component of the -coordinate. Applying the map is an application of an endomorphism over the curve. The exact mechanics involved are complicated, but when the curve has a prime number of points (and thus a prime "order") the effect of the endomorphism is to multiply the point by a scalar in which is also a primitive cube root in the scalar field.

Curve point compression

Given a point on the curve , we know that its negation is also on the curve. To uniquely specify a point, we need only encode its -coordinate along with the sign of its -coordinate.

Serialization

As mentioned in the Fields section, we can interpret the least significant bit of a field element as its "sign", since its additive inverse will always have the opposite LSB. So we record the LSB of the -coordinate as sign.

Pallas and Vesta are defined over the and fields, which elements can be expressed in bits. This conveniently leaves one unused bit in a 32-byte representation. We pack the -coordinate sign bit into the highest bit in the representation of the -coordinate:

         <----------------------------------- x --------------------------------->
Enc(P) = [_ _ _ _ _ _ _ _] [_ _ _ _ _ _ _ _] ... [_ _ _ _ _ _ _ _] [_ _ _ _ _ _ _ sign]
          ^                <------------------------------------->                 ^
         LSB                              30 bytes                                MSB

The "point at infinity" that serves as the group identity, does not have an affine representation. However, it turns out that there are no points on either the Pallas or Vesta curve with or . We therefore use the "fake" affine coordinates to encode , which results in the all-zeroes 32-byte array.

Deserialization

When deserializing a compressed curve point, we first read the most significant bit as ysign, the sign of the -coordinate. Then, we set this bit to zero to recover the original -coordinate.

If we return the "point at infinity" . Otherwise, we proceed to compute Here, we read the least significant bit of as sign. If sign == ysign, we already have the correct sign and simply return the curve point . Otherwise, we negate and return .

Cycles of curves

Let be an elliptic curve over a finite field where is a prime. We denote this by and we denote the group of points of over with order For this curve, we call the "base field" and the "scalar field".

We instantiate our proof system over the elliptic curve . This allows us to prove statements about -arithmetic circuit satisfiability.

(aside) If our curve is over why is the arithmetic circuit instead in ? The proof system is basically working on encodings of the scalars in the circuit (or more precisely, commitments to polynomials whose coefficients are scalars). The scalars are in when their encodings/commitments are elliptic curve points in .

However, most of the verifier's arithmetic computations are over the base field and are thus efficiently expressed as an -arithmetic circuit.

(aside) Why are the verifier's computations (mainly) over ? The Halo 2 verifier actually has to perform group operations using information output by the circuit. Group operations like point doubling and addition use arithmetic in , because the coordinates of points are in

This motivates us to construct another curve with scalar field , which has an -arithmetic circuit that can efficiently verify proofs from the first curve. As a bonus, if this second curve had base field it would generate proofs that could be efficiently verified in the first curve's -arithmetic circuit. In other words, we instantiate a second proof system over forming a 2-cycle with the first:

TODO: Pallas-Vesta curves

Reference: https://github.com/zcash/pasta

Hashing to curves

Sometimes it is useful to be able to produce a random point on an elliptic curve corresponding to some input, in such a way that no-one will know its discrete logarithm (to any other base).

This is described in detail in the Internet draft on Hashing to Elliptic Curves. Several algorithms can be used depending on efficiency and security requirements. The framework used in the Internet Draft makes use of several functions:

  • hash_to_field: takes a byte sequence input and maps it to a element in the base field
  • map_to_curve: takes an element and maps it to .

TODO: Simplified SWU

Reference: https://eprint.iacr.org/2019/403.pdf

References

Polynomial commitment using inner product argument

We want to commit to some polynomial , and be able to provably evaluate the committed polynomial at arbitrary points. The naive solution would be for the prover to simply send the polynomial's coefficients to the verifier: however, this requires communication. Our polynomial commitment scheme gets the job done using communication.

Setup

Given a parameter we generate the common reference string defining certain constants for this scheme:

  • is a group of prime order
  • is a vector of random group elements;
  • is a random group element; and
  • is the finite field of order

Commit

The Pedersen vector commitment is defined as

for some polynomial and some blinding factor Here, each element of the vector is the coefficient for the th degree term of and is of maximal degree

Open (prover) and OpenVerify (verifier)

The modified inner product argument is an argument of knowledge for the relation

where is composed of increasing powers of the evaluation point This allows a prover to demonstrate to a verifier that the polynomial contained “inside” the commitment evaluates to at and moreover, that the committed polynomial has maximum degree

The inner product argument proceeds in rounds. For our purposes, it is sufficient to know about its final outputs, while merely providing intuition about the intermediate rounds. (Refer to Section 3 in the Halo paper for a full explanation.)

Before beginning the argument, the verifier selects a random group element and sends it to the prover. We initialize the argument at round with the vectors and In each round :

  • the prover computes two values and by taking some inner product of with and . Note that are in some sense "cross-terms": the lower half of is used with the higher half of and , and vice versa:

  • the verifier issues a random challenge ;
  • the prover uses to compress the lower and higher halves of , thus producing a new vector of half the original length The vectors and are similarly compressed to give and .
  • , and are input to the next round

Note that at the end of the last round we are left with , , each of length 1. The intuition is that these final scalars, together with the challenges and "cross-terms" from each round, encode the compression in each round. Since the prover did not know the challenges in advance, they would have been unable to manipulate the round compressions. Thus, checking a constraint on these final terms should enforce that the compression had been performed correctly, and that the original satisfied the relation before undergoing compression.

Note that are simply rearrangements of the publicly known with the round challenges mixed in: this means the verifier can compute independently and verify that the prover had provided those same values.

Recursion

Alternative terms: Induction; Accumulation scheme; Proof-carrying data

However, the computation of requires a length- multiexponentiation where is composed of the round challenges arranged in a binary counting structure. This is the linear-time computation that we want to amortise across a batch of proof instances. Instead of computing notice that we can express as a commitment to a polynomial

where is a polynomial with degree

Since is a commitment, it can be checked in an inner product argument. The verifier circuit witnesses and brings out as public inputs to the proof The next verifier instance checks using the inner product argument; this includes checking that evaluates at some random point to the expected value for the given challenges Recall from the previous section that this check only requires work.

At the end of checking and the circuit is left with a new along with the challenges sampled for the check. To fully accept as valid, we should perform a linear-time computation of . Once again, we delay this computation by witnessing and bringing out as public inputs to the proof

This goes on from one proof instance to the next, until we are satisfied with the size of our batch of proofs. We finally perform a single linear-time computation, thus deciding the validity of the whole batch.

We recall from the section Cycles of curves that we can instantiate this protocol over a two-cycle, where a proof produced by one curve is efficiently verified in the circuit of the other curve. However, some of these verifier checks can actually be efficiently performed in the native circuit; these are "deferred" to the next native circuit (see diagram below) instead of being immediately passed over to the other curve.